Pagini recente » Cod sursa (job #2393508) | Cod sursa (job #1230298) | Cod sursa (job #1013590) | Cod sursa (job #2872489) | Cod sursa (job #2483635)
#include <iostream>
#include <cstdio>
#include <vector>
#define NMAX 100000
#define UNVISITED -1
using namespace std;
int dfsNumberCounter,numSCC;
int id[NMAX+1],low[NMAX+1];
bool onStack[NMAX+1];
vector <int> Stack;
vector <int> G[NMAX+1];
vector <int> components[NMAX+1];
void tarjanSCC(int nod){
int to;
id[nod] = low[nod] = dfsNumberCounter++;
Stack.push_back(nod);
onStack[nod] = true;
for(int j=0;j<(int)G[nod].size();j++){
to = G[nod][j];
if(id[to] == UNVISITED)
tarjanSCC(to);
if(onStack[to] == true)
low[nod] = min(low[nod], low[to]);
}
if(low[nod] == id[nod]){
do{
to = Stack.back();
Stack.pop_back();
components[numSCC].push_back(to);
onStack[to] = false;
}while(to != nod);
numSCC++;
}
}
int main()
{
FILE *fin, *fout;
int n,e,i,j,u,v;
fin = fopen("ctc.in","r");
fout = fopen("ctc.out","w");
fscanf(fin,"%d %d",&n,&e);
for(i=0;i<e;i++){
fscanf(fin,"%d %d",&u,&v);
G[u].push_back(v);
}
for(i=1;i<=n;i++)
id[i] = UNVISITED;
for(i=1;i<=n;i++)
if(id[i] == UNVISITED)
tarjanSCC(i);
fprintf(fout,"%d\n",numSCC);
for(i=0;i<numSCC;i++){
for(j=0;j<(int)components[i].size();j++)
fprintf(fout,"%d ",components[i][j]);
fprintf(fout,"\n");
}
fclose(fin);
fclose(fout);
return 0;
}