Pagini recente » Cod sursa (job #1695919) | Cod sursa (job #903389) | Cod sursa (job #1067299) | Cod sursa (job #868132) | Cod sursa (job #444291)
Cod sursa(job #444291)
#include <cstdio>
#include <vector>
#include <stack>
#include <bitset>
#include <algorithm>
using namespace std;
FILE* fin=fopen("ctc.in","r");
FILE* fout=fopen("ctc.out","w");
#define MAXN 100010
typedef vector<int>::iterator iter;
int index[MAXN],lowlink[MAXN];
vector<vector<int> > ctc;
bitset<MAXN> inStack;
vector<int> g[MAXN],comp;
stack<int> s;
int n,m,idx=1;
void tarjan(int nod){
index[nod]=lowlink[nod]=idx;
idx++;
s.push(nod),inStack[nod]=true;
for(iter it=g[nod].begin();it!=g[nod].end();it++){
if(index[*it]==-1){
tarjan(*it);
lowlink[nod]=min(lowlink[nod],lowlink[*it]);
}else if(inStack[*it]){
lowlink[nod]=min(lowlink[nod],lowlink[*it]);
}
}
if(index[nod]==lowlink[nod]){
int snod;
comp.clear();
do{
snod=s.top(),s.pop(),inStack[snod]=false;;
comp.push_back(snod);
}while(snod!=nod);
ctc.push_back(comp);
}
}
int main(){
fscanf(fin,"%d %d\n",&n,&m);
for(int i=1;i<=n;i++){
index[i]=-1;
}
int x,y;
for(int i=1;i<=m;i++){
fscanf(fin,"%d %d\n",&x,&y);
g[x].push_back(y);
}
for(int i=1;i<=n;i++){
if(index[i]==-1){
tarjan(i);
}
}
fprintf(fout,"%d\n",ctc.size());
for(int i=0;i<ctc.size();i++){
for(iter it=ctc[i].begin();it!=ctc[i].end();++it){
fprintf(fout,"%d ",*it);
}
fputc('\n',fout);
}
fclose(fin);
fclose(fout);
return 0;
}