Cod sursa(job #2027361)

Utilizator lauyoo46Ile Paul lauyoo46 Data 25 septembrie 2017 22:32:48
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
#define nmax 100005
using namespace std;

int n, m, nr, nrctc;
vector <int> G[nmax];
vector <int> GT[nmax];
vector <bool> viz(nmax);
vector <int> ctc[nmax];
vector <int> postord(nmax);

void read()
{
    ifstream f("ctc.in");
    f >> n >> m;
    for(int i=0, x, y; i<m; ++i)
    {
        f >> x >> y;
        G[x].push_back(y);
        GT[y].push_back(x);
    }
    f.close();
}

void dfs(int node)
{
    viz[node]=true;
    for(int i=0; i<G[node].size(); ++i)
        if(!viz[G[node][i]])
        dfs(G[node][i]);
    postord[++nr]=node;
}

void dfst(int node)
{
    viz[node]=false;
    ctc[nrctc].push_back(node);
    for(int i=0; i<GT[node].size(); ++i)
        if(viz[GT[node][i]])
        dfst(GT[node][i]);
}

void solve()
{
    for(int i=1; i<=n; ++i)
        if(!viz[i])
        dfs(i);

    for(int i=n; i; --i)
    {
        if(viz[postord[i]])
        {
            ++nrctc;
            dfst(postord[i]);
        }
    }
}

void out()
{
    ofstream g("ctc.out");
    g << nrctc << '\n';
    for(int i=1; i<=nrctc; ++i)
    {
        for(int j=0; j<ctc[i].size(); ++j)
            g << ctc[i][j] << ' ';
        g << '\n';
    }
    g.close();
}

int main()
{
    read();
    solve();
    out();
    /**
    10 13
1 2
2 4
4 6
6 5
5 3
3 6
4 9
9 1
7 1
7 9
7 3
8 10
10 8
**/
    return 0;
}