Cod sursa(job #2783180)

Utilizator vmnechitaNechita Vlad-Mihai vmnechita Data 13 octombrie 2021 22:21:29
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
#define pb push_back
#define NMAX 100005

using namespace std;

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

stack < int > s;
vector < int > v1[NMAX], v2[NMAX], r[NMAX];
bitset < NMAX > viz1, viz2;
int nr;

void dfs1(int k);
void dfs2(int k);

int main()
{
    int n, m, x, y, i;

    fin >> n >> m;
    while(m--)
    {
        fin >> x >> y;
        v1[x].pb(y);
        v2[y].pb(x);
    }

    for(i = 1; i <= n; i++) if(viz1[i] == 0) dfs1(i);

    while(s.empty() == 0)
    {
        x = s.top();
        s.pop();

        if(viz2[x] == 0) nr++, dfs2(x);
    }

    fout << nr << '\n';
    for(i = 1; i <= nr; i++)
    {
        for(auto it:r[i]) fout << it << ' ';
        fout << '\n';
    }

    return 0;
}

void dfs1(int k)
{
    viz1[k] = 1;
    for(auto it:v1[k]) if(viz1[it] == 0) dfs1(it);
    s.push(k);
}

void dfs2(int k)
{
    viz2[k] = 1;
    for(auto it:v2[k]) if(viz2[it] == 0) dfs2(it);
    r[nr].pb(k);
}