Pagini recente » Cod sursa (job #2947631) | Cod sursa (job #2789518) | Cod sursa (job #355669) | Cod sursa (job #1665500) | Cod sursa (job #1182571)
#include <iostream>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
using namespace std;
int n,m;
vector<int> v1[100500];
vector<int> v2[100500];
bool markA[100500];
stack<int> finish;
vector< stack<int> > solution;
void dfsA(int node){
markA[node] = true;
for(int i = 0; i < v1[node].size(); i++){
if(!markA[v1[node][i]])
dfsA(v1[node][i]);
}
finish.push(node);
}
void dfsB(int node,int &cnt){
markA[node] = true;
solution[cnt].push(node);
for(int i =0 ; i < v2[node].size(); i++){
if(!markA[v2[node][i]])
dfsB(v2[node][i],cnt);
}
}
int main(){
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i = 0; i < m; i++){
int x,y;
scanf("%d %d",&x,&y);
v1[x].push_back(y);
v2[y].push_back(x);
}
for(int i =1 ; i <= n; i++){
if(!markA[i])
dfsA(i);
}
memset(markA,0,sizeof markA);
int cnt =0;
stack<int>S;
solution.push_back(S);
while(!finish.empty()){
if(markA[finish.top()]){
finish.pop();
continue;
}
dfsB(finish.top(),cnt);
finish.pop();
cnt++;
stack<int>S;
solution.push_back(S);
}
cout << cnt << endl;
for(int i =0 ; i < cnt; i++){
while(!solution[i].empty()){
cout << solution[i].top() << " ";
solution[i].pop();
}
cout << endl;
}
}