Cod sursa(job #1963463)

Utilizator teo.serbanescuTeo Serbanescu teo.serbanescu Data 12 aprilie 2017 15:54:30
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <vector>
#include <string.h>
#include <stack>
 
using namespace std;
 
fstream f("ctc.in", ios::in);
fstream g("ctc.out", ios::out);
 
int const nmax = 100005;
 
vector <int> a[nmax], aT[nmax], tc[nmax];
stack <int> S;
 
int n, m, i, j, x, y, comp, viz[nmax];
 
void citire()
{
    f >> n >> m;
    for (i = 1; i <= m; i++)
    {
        f >> x >> y;
        a[x].push_back(y);
        aT[y].push_back(x);
    }
}
 
void dfs(int nc)
{
    S.push(nc);
    for (vector<int>::iterator it = a[nc].begin(); it != a[nc].end(); ++it)
    {
        if(!viz[*it])
        {
            viz[*it] = 1;
            dfs(*it);
        }
    }
}

void dfsT(int nc)
{
    tc[comp].push_back(nc);
    for (vector<int>::iterator it = aT[nc].begin(); it != aT[nc].end(); ++it)
    {
        if(!viz[*it])
        {
            viz[*it] = 1;
            dfsT(*it);
        }
    }
}

 
int main()
{
    citire();
    comp = 0;
    memset(viz, 0, sizeof(viz));
    for (i = 1; i <= n; i++) {
        if (!viz[i]) {
            //comp++;
            viz[i] = 1;
            dfs(i);
        }
    }
    memset(viz, 0, sizeof(viz));
    while (!S.empty()) {
        int nod = S.top();
        S.pop();
        if (!viz[nod]) {
            viz[nod] = 1;
            dfsT(nod);
            comp++;
            //start.push_back(nod);
        }
    }
    g << comp << '\n';
    for (int i = 0; i < comp; ++i) {
        for (vector<int>::iterator it = tc[i].begin(); it != tc[i].end(); ++it) {
            g << *it << " ";
        }
        g << '\n';
    }
 
    return 0;
}