Cod sursa(job #1569246)

Utilizator fromzerotoheroFROM ZERO fromzerotohero Data 15 ianuarie 2016 10:47:19
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#include <stack>

#define nmax 100001

using namespace std;

int n, m, numComp;
bool seen[nmax];
stack <int> S;
vector <int> G[nmax], GT[nmax], Comp[nmax];

void DFS(int nod)
{

    seen[nod] = true;

    for (int i = 0; i < G[nod].size(); i++)
        if (!seen[ G[nod][i] ])
            DFS(G[nod][i]);

    S.push(nod);

}

void reverseDFS(int nod)
{

    seen[nod] = true;

    Comp[numComp].push_back(nod);

    for (int i = 0 ; i < GT[nod].size(); i++)
        if (!seen[ GT[nod][i] ])
            reverseDFS(GT[nod][i]);

}

int main()
{

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

    fi >> n >> m;

    for (int i = 1; i <= m; i++)
    {

        int a, b;

        fi >> a >> b;
        G[a].push_back(b);
        GT[b].push_back(a);

    }

    for (int i = 1; i <= n; i++)
        if (!seen[i])
            DFS(i);

    memset(seen, 0, nmax);

    while (!S.empty())
    {

        int nod = S.top();
        S.pop();

        if (!seen[nod])
        {
            numComp++;
            reverseDFS(nod);
        }

    }

    fo << numComp << "\n";
    for (int i = 1; i <= numComp; i++)
    {
        for (int j = 0; j < Comp[i].size(); j++)
            fo << Comp[i][j] << " ";
        fo << "\n";
    }

    fi.close();
    fo.close();

    return 0;
}