Cod sursa(job #2612266)

Utilizator k2e0e0w3qDumitrescu Gheorghe k2e0e0w3q Data 8 mai 2020 18:50:16
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>
#define N 100000
using namespace std;

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

bitset <N+1> seen;
vector <int> G[N+1], GT[N+1], S, tmp;
vector <vector <int>> ans;

void dfs (int x) {
    seen[x]=1;
    S.push_back(x);
    for (auto it: G[x])
        if (!seen[it])
            dfs(it);
}

void dfsT (int x) {
    seen[x]=1;
    for (auto it: GT[x])
        if (!seen[it])
            dfsT(it);
    tmp.push_back(x);
}

int main () {
    int n, m;
    ios::sync_with_stdio(false);
    fin >> n >> m;

    int i, j;
    for (; m; m--) {
        fin >> i >> j;
        G[i].push_back(j);
        GT[j].push_back(i);
    }

    for (i=1; i<=n; i++)
        if (!seen[i])
            dfs(i);
    seen.reset();

    int ct=0;
    for (auto it=S.rbegin(); it!=S.rend(); ++it)
        if (!seen[*it]) {
            ++ct;
            dfsT(*it);
            ans.push_back(tmp);
            tmp.clear();
        }

    fout << ans.size() << '\n';
    for (auto i: ans) {
        for (auto j: i)
            fout << j << ' ';
        fout << '\n';
    }
    return 0;
}