Pagini recente » Cod sursa (job #1855053) | Cod sursa (job #1694590) | Cod sursa (job #3337316) | Cod sursa (job #1417243) | Cod sursa (job #1182579)
#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;
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);
}
int dfsB(int node,int &cnt,int &sum){
markA[node] = true;
solution.push(node);
sum++;
for(int i =0 ; i < v2[node].size(); i++){
if(!markA[v2[node][i]])
dfsB(v2[node][i],cnt,sum);
}
}
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;
vector<int> v;
while(!finish.empty()){
if(markA[finish.top()]){
finish.pop();
continue;
}
int sum = 0;
dfsB(finish.top(),cnt,sum);
v.push_back(sum);
finish.pop();
cnt++;
}
cout << cnt << endl;
for(int i = v.size()-1; i>=0 ; i--){
while(v[i] > 0){
printf("%d ",solution.top());
v[i]--;
solution.pop();
}
printf("\n");
}
}