Cod sursa(job #1255019)

Utilizator alexb97Alexandru Buhai alexb97 Data 3 noiembrie 2014 23:59:18
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

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

vector<vector<int>>g;
vector<vector<int>>gt;
stack<int> stk;
vector<bool> s;
vector<vector<int>> sol;
int n, m, nrsol, r;

void Read();
void Dfs1(int x);
void Dfs2(int x, int r);

int main()
{
    Read();
    for(int i = 1; i <=  n; ++i)
    {
        if(!s[i])
            Dfs1(i);
    }
    s.assign(n+1, false);
    int k;
    while(!stk.empty())
    {
        k = stk.top();
        stk.pop();
        if(!s[k])
        {
            nrsol++;
            Dfs2(k, nrsol);
        }
    }
    os << nrsol << '\n';
    for(int i = 1; i <= nrsol; ++i)
    {
        for( vector<int>::iterator it = sol[i].begin(); it != sol[i].end(); ++it)
            os << *it << ' ';
        os << '\n';
    }

    is.close();
    os.close();
    return 0;
}

void Read()
{
    is >> n >> m;
    g = vector<vector<int>>(n+1);
    gt = vector<vector<int>>(n+1);
    sol = vector<vector<int>>(n+1);
    s = vector<bool>(n+1);
    int x, y;
    for(int i = 1; i <= m; ++i)
    {
        is >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
}

void Dfs1(int x)
{
    s[x] = true;
    for(vector<int>::iterator it = g[x].begin(); it != g[x].end(); ++it)
        if(!s[*it])
            Dfs1(*it);
    stk.push(x);
}

void Dfs2(int x, int r)
{
    s[x] = true;
    sol[r].push_back(x);
    for(const auto& y : gt[x])
        if(!s[y])
            Dfs2(y, r);
}