Pagini recente » Cod sursa (job #1958879) | Cod sursa (job #1319974) | Cod sursa (job #1250470) | Cod sursa (job #2411853) | Cod sursa (job #2483630)
#include <iostream>
#include <cstdio>
#include <vector>
#define NMAX 100000
#define UNVISITED -1
using namespace std;
int dfsNumberCounter,numSCC;
int id[NMAX],low[NMAX];
bool onStack[NMAX];
vector <int> Stack;
vector <int> G[NMAX];
vector <int> components[NMAX];
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]){
to = Stack.back();
Stack.pop_back();
while(to != nod){
components[numSCC].push_back(to);
to = Stack.back();
Stack.pop_back();
}
components[numSCC].push_back(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;
}