Cod sursa(job #1917436)

Utilizator pusi23Faier Andreea pusi23 Data 9 martie 2017 12:15:26
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

struct nod {
        int a;
        nod *x;
} *L1[100002], *L2[100002],*comp[100002];


int post[10002],n,m,cnt,A,B,i;
char v[100002];

void df1(int nodd)
{
    int nr;
    nr=0;
    nod *q;
    v[nodd]=1;

    for(q=L1[nodd];q;q=q->x)
        if(v[q->a]==0) df1(q->a);
    post[nr++]=nodd;
}

void df2(int nodd)
{
    nod *q;
    v[nodd]=0;

    q=new nod;
    q->a=nodd;
    q->x=comp[cnt];
    comp[cnt]=q;

    for(q=L2[nodd];q;q=q->x)
        if(v[q->a]==1) df2(q->a);
}


int main()
{
    nod *q;
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>A>>B;
        q= new nod;
        q->a=B;
        q->x=L1[A];

        q=new nod;
        q->a=A;
        q->x=L1[A];
        L1[A]=q;
    }

    for(i=1;i<=n;i++)
        if(v[i] == 0) df1(i);

    for(i=n;i>0;i--)
        if(v[post[i]] == 1 )
    {
        cnt++;
        df2(post[i]);
    }
    g<<cnt;

    for(i=1;i<=cnt;i++)
    {
        g<<endl;
        for(q=comp[i];q;q=q->x)
            g<<q->a<<" ";
    }

    f.close();
    g.close();

    return 0;
}