Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- struct node{
- int czasy;
- vector<int> polaczenia;
- int self = 100000000;
- };
- node graph[2000];
- node graph2[2000];
- vector <int> przechowanie;
- int kolejnosc = 1;
- void DFS(int START = 1, int value = -1)
- {
- graph[START].self = value + 1;
- int ile;
- for(int i = 0; i < graph[START].polaczenia.size(); i++){
- ile = graph[START].polaczenia[i];
- if(graph[START].self + 1 < graph[ile].self){
- DFS(ile,graph[START].self);
- }
- }
- graph[START].czasy = kolejnosc;
- kolejnosc++;
- }
- void DFS2(int START = 1, int value = -1)
- {
- graph2[START].self = value + 1;
- int ile;
- for(int i = 0; i < graph2[START].polaczenia.size(); i++){
- ile = graph2[START].polaczenia[i];
- if(graph2[ile].self == 100000000){
- DFS2(ile,graph2[START].self);
- }
- }
- przechowanie.push_back(START);
- }
- bool pairCompare(pair<int, int> first, pair<int, int> second) {
- return first.second > second.second;
- }
- int main(){
- int n,m,from,to;
- cin >> n >> m;
- for(int i = 0;i < m; i++)
- {
- cin >> from >> to;
- graph[from].polaczenia.push_back(to);
- graph2[to].polaczenia.push_back(from);
- }
- DFS();
- // for(int i = 1;i <= n; i++)
- // {
- // cout << graph[i].czasy << " ";
- // }
- cout << endl;
- pair<int,int> tab[n];
- for(int i = 0;i < n; i++)
- {
- tab[i] = {i+1,graph[i+1].czasy};
- }
- sort(tab, tab + n, pairCompare);
- // for(int i = 0;i < n; i++)
- // {
- // cout << tab[i].first << " " << tab[i].second << endl;
- // }
- vector<vector <int> > wynik;
- for(int i = 0; i < n; i++){
- if(graph2[tab[i].first].self == 100000000)
- {
- przechowanie.clear();
- DFS2(tab[i].first);
- sort(przechowanie.begin(), przechowanie.end());
- // for(int j = 0; j < przechowanie.size(); j++){
- // cout << przechowanie[j] << " ";
- // }
- // cout << endl;
- wynik.push_back(przechowanie);
- }
- }
- for(int i = 0;i < wynik.size(); i++)
- {
- for(int j = 0; j < wynik[i].size(); j++){
- cout << wynik[i][j] << " ";
- }
- cout << endl;
- }
- }
Add Comment
Please, Sign In to add comment