Cod sursa(job #1896020)

Utilizator ciprianprohozescuProhozescu Ciprian ciprianprohozescu Data 28 februarie 2017 13:21:24
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <vector>
#define NMAX 100010

using namespace std;

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

vector<int> G[NMAX];
vector<int> GT[NMAX];
vector<int> CTC[NMAX];

int n, m, nr, nrc;
int post[NMAX];
bool viz[NMAX];

void citire();
void DFS(int x);
void DFST(int x);
void afisare();

int main()
{
    int i;
    citire();
    for (i = 1; i <= n; i++)
    {
        if (!viz[i])
            DFS(i);
    }
    for (i = n; i >= 1; i--)
    {
        if (viz[post[i]])
        {
            nrc++;
            DFST(post[i]);
        }
    }
    afisare();
    return 0;
}

void citire()
{
    int i, a, b;
    fin >> n >> m;
    for (i = 0; i < m; i++)
    {
        fin >> a >> b;
        G[a].push_back(b);
        GT[b].push_back(a);
    }
}
void DFS(int x)
{
    int i;
    viz[x] = 1;
    for (i = 0; i < G[x].size(); i++)
    {
        if (!viz[G[x][i]])
            DFS(G[x][i]);
    }
    post[++nr] = x;
}
void DFST(int x)
{
    int i;
    viz[x] = 0;
    CTC[nrc].push_back(x);
    for (i = 0; i < GT[x].size(); i++)
    {
        if (viz[GT[x][i]])
            DFST(GT[x][i]);
    }
}
void afisare()
{
    int i, j;
    fout << nrc << '\n';
    for (i = 1; i <= n; i++)
    {
        for (j = 0; j < CTC[i].size(); j++)
            fout << CTC[i][j] << ' ';
        fout << '\n';
    }
    fout.close();
}