Pagini recente » Cod sursa (job #1701702) | Cod sursa (job #893752) | Cod sursa (job #385710) | Cod sursa (job #187678) | Cod sursa (job #1894834)
#include <stdio.h>
#include <vector>
#define N 100005
using namespace std;
vector<int> g[N],gt[N],cc[N]; ///graf, graf transpus, componente conexe
int n,m,i,j,a,b,nrcc;
int ord[N];
bool viz[N];
void sorttop(int x) ///sortare topologica
{
int i;
viz[x]=true;
for(i=0;i<g[x].size();i++)
if(!viz[g[x][i]])
sorttop(g[x][i]);
ord[++ord[0]]=x;
}
void dfs(int x)
{
int i;
//printf("%d %d\n",nrcc,x);
cc[nrcc].push_back(x);
viz[x]=true;
for(i=0;i<gt[x].size();i++)
if(!viz[gt[x][i]])
dfs(gt[x][i]);
}
int main()
{
FILE *f1,*f2;
f1=fopen("ctc.in","r");
f2=fopen("ctc.out","w");
fscanf(f1,"%d%d",&n,&m);
for(i=0;i<m;i++)
{
fscanf(f1,"%d%d",&a,&b);
g[a].push_back(b);
gt[b].push_back(a);
}
for(i=1;i<=n;i++)
if(!viz[i])
sorttop(i);
//for(i=1;i<=ord[0];i++)
//printf("%d ",ord[i]);
for(i=1;i<=n;i++)
viz[i]=false;
for(i=ord[0];i>0;i--)
if(!viz[ord[i]])
{
//printf("%d ",ord[i]);
nrcc++;
dfs(ord[i]);
}
fprintf(f2,"%d\n",nrcc);
for(i=1;i<=nrcc;i++)
{
for(j=0;j<cc[i].size();j++)
fprintf(f2,"%d ",cc[i][j]);
fprintf(f2,"\n");
}
return 0;
}