Cod sursa(job #1262495)

Utilizator andi12Draghici Andrei andi12 Data 13 noiembrie 2014 11:38:29
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <cstdio>

using namespace std;
const int N=100001;
const int M=200001;
int lst1[N],urm1[M],vf1[M];
int lst2[N],urm2[M],vf2[M];
bool marcat[N];
int v[N];
int p,nr,ras;
void ad1(int x,int y)
{
    p++;
    vf1[p]=y;
    urm1[p]=lst1[x];
    lst1[x]=p;
}
void ad2(int x,int y)
{
    p++;
    vf2[p]=y;
    urm2[p]=lst2[x];
    lst2[x]=p;
}
void dfs1(int x)
{
    int poz=lst1[x];
    marcat[x]=1;
    while(poz!=0)
    {
        if(marcat[vf1[poz]]==0)
            dfs1(vf1[poz]);
        poz=urm1[poz];
    }
    v[++nr]=x;
}
void dfs2(int x)
{
    int poz=lst2[x];
    marcat[x]=1;
    while(poz!=0)
    {
        if(marcat[vf2[poz]]==0)
            dfs2(vf2[poz]);
        poz=urm2[poz];
    }
}
FILE *in,*out;
void dfs3(int x)
{
    int poz=lst2[x];
    marcat[x]=1;
    fprintf(out,"%d ",x);
    while(poz!=0)
    {
        if(marcat[vf2[poz]]==0)
            dfs3(vf2[poz]);
        poz=urm2[poz];
    }
}
int main()
{
    in=fopen("ctc.in","r");
    out=fopen("ctc.out","w");
    int n,m,i,j,x,y,poz;
    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d",&x,&y);
        ad1(x,y);
        ad2(y,x);
    }
    marcat[0]=1;
    poz=1;
    for(i=1;i<=n;i++)
        if(marcat[i]==0)
            dfs1(i);
    for(i=1;i<=n;i++)
        marcat[i]=0;
    for(i=n;i>=1;i--)
    {
        if(marcat[i]==0)
        {
            ras++;
            dfs2(v[i]);
        }
    }
    fprintf(out,"%d\n",ras);
    for(i=1;i<=n;i++)
        marcat[i]=0;
    for(i=n;i>=1;i--)
    {
        if(marcat[i]==0)
        {
            dfs3(v[i]);
            fprintf(out,"\n");
        }
    }
    return 0;
}