Pagini recente » Cod sursa (job #718123) | Cod sursa (job #379349) | Cod sursa (job #2971555) | Cod sursa (job #1816862) | Cod sursa (job #1352462)
#include <cstdio>
#define nmax 100010
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
void read();
void tarjan(long);
void sol();
long n,m;
vector < long > graph[nmax],con,idx,lowlink,in_stack;
vector <vector < long > > res;
stack < long > s;
long indl;
int main(){
freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
read();
idx.resize(n);
lowlink.resize(n);
in_stack.resize(n);
idx.assign(n,-1);
in_stack.assign(n,0);
sol();
return 0;
}
void read(){
scanf("%ld %ld ",&n,&m);
long x,y;
while(m--){
scanf("%ld %ld ",&x,&y);
graph[x - 1].push_back(y - 1);
}
}
void tarjan(long x){
idx[x] = lowlink[x] = indl;
indl++;
s.push(x);
in_stack[x] = true;
for(vector < long > :: iterator it = graph[x].begin();it != graph[x].end();++it){
if(idx[*it] == -1){
tarjan(*it);
lowlink[x] = min(lowlink[x],lowlink[*it]);
}
else if(in_stack[*it] == true){
lowlink[x] = min(lowlink[x],lowlink[*it]);
}
}
if(idx[x] == lowlink[x]){
con.clear();
long node;
do{
node = s.top();
con.push_back(node);
s.pop();
in_stack[node] = false;
}while(node != x);
res.push_back(con);
}
}
void sol(){
for(long it = 0;it < n;++it)
if(idx[it] == -1)tarjan(it);
printf("%ld\n",res.size());
for(long i = 0;i < res.size();++i){
for(long j = 0;j < res[i].size();++j)printf("%ld ",res[i][j] + 1);
printf("\n");
}
}