Cod sursa(job #2444994)

Utilizator blotucosmincosmin blotucosmin Data 2 august 2019 10:11:38
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector <int> v[NMAX], a[NMAX], b[NMAX];
int viz[NMAX], x, y, n, t, comp, i, j;
stack <int> S;
void dfs(int k)
{
    viz[k] = 1;
    for(int i = 0; i < v[k].size(); ++ i)
    {
        int x = v[k][i];
        if(!viz[x]) dfs(x);
    }
    S.push(k);
}
void dfs1(int k)
{
    viz[k] = 2;
    b[comp].push_back(k);
    for(int i = 0; i < a[k].size(); ++ i)
    {
        int x = a[k][i];
        if(viz[x] == 1) dfs1(x);
    }
}
int main()
{
    f >> n >> t;
    while(t --)
    {
        f >> x >> y;
        v[x].push_back(y);
        a[y].push_back(x);
    }
    for(i = 1; i <= n; ++ i)
        if(!viz[i]) dfs(i);
    while(!S.empty())
    {
        int x = S.top();
        if(viz[x] == 1)
        {
            comp ++;
            dfs1(x);
        }
        S.pop();
    }
    g << comp << "\n";
    for(i = 1; i <= comp; ++ i)
    {
        for(j = 0; j < b[i].size(); ++ j)
            g << b[i][j] << " ";
        g << "\n";
    }
    return 0;
}