Pagini recente » Cod sursa (job #247000) | Cod sursa (job #1362970) | Cod sursa (job #2883577) | Cod sursa (job #1449961) | Cod sursa (job #780354)
Cod sursa(job #780354)
/*Algoritmul lui Tarjan*/
#include<cstdio>
#include<list>
#include<stack>
#include<vector>
#define WHITE 0
#define GRAY 1
#define BLACK 2
using namespace std;
int N,M,i,j,x,y,color[100003],index[100003],low[100003],ind,q,nrctc;
list<int> L[100003];
stack<int> S;
vector<int> V[100003];
void parcurge(int x)
{ind++;
color[x]=GRAY;
index[x]=ind;
low[x]=ind;
S.push(x);
list<int>::iterator it;
for(it=L[x].begin(); it!=L[x].end(); it++)
{if(color[*it]==WHITE)
{parcurge(*it);
if(low[*it]<low[x])
low[x]=low[*it];}
if(color[*it]==GRAY)
{if(low[*it]<low[x])
low[x]=low[*it];}
}
if(low[x]==index[x])
{nrctc++;
do
{q=S.top();
V[nrctc].push_back(q);
color[q]=BLACK;
S.pop();
} while(q!=x);
}
}
int main()
{freopen("ctc.in","r",stdin);
freopen("ctc.out","w",stdout);
scanf("%d %d",&N,&M);
for(i=1; i<=M; i++)
{scanf("%d %d",&x,&y);
L[x].push_back(y);}
for(i=1; i<=N; i++)
{if(color[i]==WHITE)
parcurge(i);}
printf("%d\n",nrctc);
//vector<int>::iterator it;
for(i=1; i<=nrctc; i++)
{for(j=0; j<V[i].size(); j++)
printf("%d ",V[i][j]);
printf("\n");}
return 0;}