Pagini recente » Statistici Caia H. Cristina Elena (caiacristina00) | Monitorul de evaluare | Istoria paginii utilizator/xxspeedyxxro | Istoria paginii utilizator/mihaitacornestean | Cod sursa (job #616096)
Cod sursa(job #616096)
#include<stdio.h>
#include<vector>
using namespace std;
#define MaxN 100100
typedef vector<int>::iterator it;
vector<int> A[MaxN],B[MaxN],C[MaxN];
int N,M,nr,MAX,S[MaxN],viz[MaxN];
void citire(void)
{
int a,b;
FILE *f = fopen("ctc.in","r");
fscanf(f,"%d %d ",&N,&M);
for(int i=1;i<=M;i++)
{
fscanf(f,"%d %d",&a,&b);
A[a].push_back(b);
B[b].push_back(a);
}
fclose(f);
}
void DFBIS(int a)
{
viz[a] = 1;
for(it i=A[a].begin();i<A[a].end();i++)
if(!viz[*i])
DFBIS(*i);
S[++nr] = a;
}
void DFAFIS(int a)
{
C[MAX].push_back(a);
viz[a] = 0;
for(it i=B[a].begin();i<B[a].end();i++)
if(viz[*i])
DFAFIS(*i);
}
void kosaraju(void)
{
for(int i=1;i<=N;i++)
if(!viz[i])
DFBIS(i);
for(int i=N;i;i--)
if(viz[S[i]])
++MAX,DFAFIS(S[i]);
}
void Afis(void)
{
FILE *g = fopen("ctc.out","w");
fprintf(g,"%d\n",MAX);
for(int i=1;i<=MAX;i++,fprintf(g,"\n"))
for(it j=C[i].begin();j<C[i].end();j++)
fprintf(g,"%d ",*j);
fclose(g);
}
int main()
{
citire();
kosaraju();
Afis();
return 0;
}