Cod sursa(job #1252815)

Utilizator PintilieAndreiPintilieAndrei PintilieAndrei Data 31 octombrie 2014 12:29:24
Problema Componente tare conexe Scor 24
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
vector <int>L[100003];
vector <int>p[100003];
vector <int>tr[100003];

int n, m,k;
int V[100003], V2[100003];
int tf[100003], ctc[1000003];
ifstream fin("ctc.in");

void Citire()
{
    fin >> n >> m; //m-numarul de muchii; n-nr de noduri
    int i, x, y;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y;
        L[x].push_back(y);
    }
}

void DFS_timp_final(int x)
{
    V2[x] = 1;
    for (unsigned int i = 0; i < L[x].size(); i++)
        if (V2[L[x][i]] == 0)
            DFS_timp_final(L[x][i]);
    tf[++k]=x;
}

void Graf_Transpus()
{
    int len, i, j, k;
    for(i = 1; i <= n; i++)
    {
        len = L[i].size();
        for(j = 0; j < len; j++)
        {
            k = L[i][j];
            tr[k].push_back(i);
        }
    }
}

void DFS_tr(int x)
{
    V[x] = 1;
    ctc[x]=k;
    for (unsigned int i = 0; i < tr[x].size(); i++)
        if (V[tr[x][i]] == 0)
            DFS_tr(tr[x][i]);
}

void Afisare()
{
    ofstream fout("ctc.out");
    int i,j;
    fout<<k<<"\n";
    for (i = 1; i <= k; i++)
    {
        for(j=1;j<=n;j++)
            if(ctc[j]==i)
                fout <<j <<" ";
        fout<<" ";
    }
    fout<<"\n";
}

int main()
{
    int i,x;
    Citire();
    Graf_Transpus();
    k=0;
    for(i=1;i<=n;i++)
        if(!V2[i])
            DFS_timp_final(i);
    k=0;
    for(i=n;i>=1;i--)
    {
        if(V[tf[i]]==0)
        {
            k++;
            DFS_tr(tf[i]);
        }
    }

    Afisare();
    return 0;
}