Cod sursa(job #1105029)

Utilizator HDT_TibiHudema Dumitru Tiberiu HDT_Tibi Data 11 februarie 2014 13:04:58
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

struct Nod{int inf; Nod* leg;};
typedef Nod* nod;

nod a[100000],b[100000];

int n,m, viz[100000],viz2[100000];

void adaug(int y, int x)
{
    nod p=new Nod;
    p->inf=x;
    p->leg=a[y];
    a[y]=p;
}

void adaug2(int y, int x)
{
    nod p=new Nod;
    p->inf=x;
    p->leg=b[y];
    b[y]=p;
}


void parc(int i, int k)
{
    viz[i]=k;
    for(nod j=a[i]; j; j=j->leg) if (!viz[j->inf]) parc(j->inf,k);
}

void parc2(int i,int k)
{
    viz2[i]=k;
    for(nod j=b[i]; j; j=j->leg) if (!viz2[j->inf]) parc2(j->inf,k);
}

int main()
{
    int i,j,x,y,k=0;
    fin>>n>>m;
    for(i=1; i<=m; i++)
    {
        fin>>x>>y;
        adaug(x,y);
        adaug2(y,x);
    }
    for(i=1; i<=n; i++)
        if(!viz[i])
        {
            k++;
            parc(i,k);//for(int q=1; q<=n; q++) fout<<viz[q]<<" "; fout<<endl;
            parc2(i,k);//for(int q=1; q<=n; q++) fout<<viz2[q]<<" "; fout<<endl;
            fout<<endl;
            for(j=1; j<=n; j++)
                if(viz[j]==k)
                    if(viz[j]!=viz2[j]) viz[j]=0;
        }
    fout<<k<<"\n";
    for(i=1; i<=k; i++)
    {
        for(j=1; j<=n; j++) if (viz[j]==i) fout<<j<<" ";
        fout<<"\n";
    }

    return 0;
}