Cod sursa(job #2612261)

Utilizator k2e0e0w3qDumitrescu Gheorghe k2e0e0w3q Data 8 mai 2020 18:46:05
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 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;
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);
    fout << 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);
    }

    fout << '\n';
    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]) {
            dfsT(*it);
            ++ct;
            fout << '\n';
        }

    fout.seekp(0);
    fout << ct;
    return 0;
}