Pagini recente » Cod sursa (job #2891921) | Cod sursa (job #1147764) | Cod sursa (job #2969481) | Cod sursa (job #2534828) | Cod sursa (job #2472583)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 200002;
vector<int> adj[maxn];
vector<int> adjInv[maxn];
vector<int> dfs;
vector<int> components[maxn];
bool used[maxn];
int value[maxn];
void DFS(int v){
if(used[v]) return;
used[v] = true;
for(int i=0; i<adj[v].size(); i++){
DFS(adj[v][i]);
}
dfs.push_back(v);
}
void DFSvalue(int v, int val){
if(value[v]!=0) return;
value[v]=val;
components[val].push_back(v);
for(int i=0; i<adjInv[v].size(); i++){
DFSvalue(adjInv[v][i], val);
}
}
int main()
{
int n;
int m;
cin >> n >> m;
for(int i=0; i<m; i++){
int first, second;
cin >> first >> second;
adj[first].push_back(second);
adjInv[second].push_back(first);
}
for(int i=0; i<n; i++){
if(used[i]) continue;
DFS(i);
}
int valueNumber = 1;
for(int i=dfs.size()-1; i>=0; i--){
if(value[dfs[i]]!=0) continue;
DFSvalue(dfs[i], valueNumber);
valueNumber++;
}
cout << valueNumber-1 << endl;
for(int i=1; i<valueNumber; i++){
for(int j=0; j<components[i].size(); j++){
cout << components[i][j] << " ";
}
cout << endl;
}
return 0;
}
/*
10 12
0 1
1 2
2 3
3 1
2 4
4 5
5 6
6 4
5 7
7 6
8 4
8 9
*/