Cod sursa(job #1638037)

Utilizator FeriCsiki Francisc Alexandru Feri Data 7 martie 2016 20:43:14
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <fstream>
using namespace std;

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

const int N = 100003,M=200003;

int lst1[N],lst2[N],vf1[N],vf2[N],urm1[M],urm2[M],c[N],viz2[N],sol,lst3[N],urm3[M],vf3[N];
int nr2,nr3,nr1;
bool viz[N];
void adauga(int x,int y)
{
    nr1++;
    vf1[nr1]=y;
    urm1[nr1]=lst1[x];
    lst1[x]=nr1;
}
void adauga2(int x,int y)
{
    nr2++;
    vf2[nr2]=y;
    urm2[nr2]=lst2[x];
    lst2[x]=nr2;
}
void adauga3(int x,int y)
{
    nr3++;
    vf3[nr3]=y;
    urm3[nr3]=lst3[x];
    lst3[x]=nr3;
}
void dfs1(int x)
{
    int y,p;
    p=lst1[x];
    viz[x]=true;
    while(p!=0)
    {
        y=vf1[p];
        if(!viz[y])
            dfs1(y);
        p=urm1[p];
    }
    c[++sol]=x;
}
void dfs2(int x)
{
    int p, y;
    viz2[x] = true;
    p = lst2[x];
    //out << x << " ";
    adauga3(sol, x);
    while(p != 0)
    {
        y = vf2[p];
        if(!viz2[y]) dfs2(y);
        p = urm2[p];
    }
    //c[++nr2] = x;
}

int main()
{
    int n,m,i,x,y,p;
    in>>n>>m;
    for(i=1; i<=m; i++)
    {
        in>>x>>y;
        adauga(x,y);
        adauga2(y,x);
    }
    for(i = 1; i <= n; i++)
        if(!viz[i])
            dfs1(i);
    sol = 0;
    for(i = n; i >= 1; i--)
        if(!viz2[c[i]])
        {
            sol++;
            dfs2(c[i]);
            //out << "\n";
        }
    out<<sol<<'\n';
    for(i=1; i<=sol; i++)
    {
        p=lst3[i];
        while(p!=0)
        {
            y = vf3[p];
            out << y << " ";
            p = urm3[p];
        }
        out<<'\n';
    }
    return 0;
}