Pagini recente » Cod sursa (job #2503083) | Cod sursa (job #2365758) | Cod sursa (job #1932426) | Cod sursa (job #2067209) | Cod sursa (job #566416)
Cod sursa(job #566416)
#include <stdio.h>
#include <vector>
#include <stack>
#define N 100001
#define INF 1<<31
using namespace std;
int n,m,nr,rez;
int index[N],L[N];
bool VIZ[N];
vector <int> A[N],R[N];
stack <int> S;
FILE *f, *g;
int minim(int a, int b)
{
if (a<=b)
return a;
else
return b;
}
void citire()
{
int i,x,y;
fscanf(f,"%d %d",&n,&m);
for (i=1;i<=m;++i)
{
fscanf(f,"%d %d",&x,&y);
A[x].push_back(y);
}
}
void comp_strong(int nod)
{
vector <int> :: iterator it;
int v;
index[nod]=L[nod]=nr++;
VIZ[nod]=1;
S.push(nod);
for (it=A[nod].begin();it!=A[nod].end();it++)
if (index[*it]==INF)
{
comp_strong(*it);
L[nod]=minim(L[nod],L[*it]);
}
else if (VIZ[*it]==1)
L[nod]=minim(L[nod],index[*it]);
if (index[nod]==L[nod])
{
v=S.top();
S.pop();
VIZ[v]=0;
rez++;
R[rez].push_back(v);
while (v!=nod)
{
v=S.top();
VIZ[v]=0;
S.pop();
R[rez].push_back(v);
}
}
}
void tarjan()
{
int i;
for (i=1;i<=n;++i)
index[i]=L[i]=INF;
for (i=1;i<=n;++i)
if (index[i]==INF)
comp_strong(i);
}
void afisare()
{
int i;
vector <int> :: iterator it;
fprintf(g,"%d\n",rez);
for (i=1;i<=rez;i++)
{
for (it=R[i].begin();it!=R[i].end();it++)
fprintf(g,"%d ",*it);
fprintf(g,"\n");
}
}
int main()
{
f=fopen("ctc.in","r");
g=fopen("ctc.out","w");
citire();
tarjan();
afisare();
fclose(f);
fclose(g);
return 0;
}