Cod sursa(job #2794387)

Utilizator CaptnBananaPetcu Tudor CaptnBanana Data 4 noiembrie 2021 19:29:29
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <bits/stdc++.h>

using namespace std;

ifstream f("ctc.in");
ofstream g("ctc.out");

const int N = 1e5 + 1;
int n, m, x, y, fin[N], cnt;
vector<int> c[N], ct[N];
bool vis[N];

void dfs(int nod){
    vis[nod] = 1;
    for(int y: c[nod]){
        if(!vis[y])
            dfs(y);
    }

    fin[++cnt] = nod;
}

void dfsT(int nod, bool scriem){
    vis[nod] = 1;
    for(int y: ct[nod]){
        if(!vis[y])
            dfsT(y, scriem);
    }

    if(scriem)
        cout << nod << ' ';
}

int main(){
    f >> n >> m;
    for(int i = 0; i < m; i++){
        f >> x >> y;
        c[x].push_back(y);
        ct[y].push_back(x);
    }

    f.close();
    for(int i = 1; i <= n; i++){
        if(!vis[i])
            dfs(i);
    }

    cnt = 0;
    memset(vis, 0, sizeof(vis));
    for(int i = n; i >= 1; i--){
        if(!vis[fin[i]]){
            cnt++;
            dfsT(fin[i], 0);
        }
    }

    memset(vis, 0, sizeof(vis));
    g << cnt << '\n';
    for(int i = n; i >= 1; i--){
        if(!vis[fin[i]]){
            dfsT(fin[i], 1);
            g << '\n';
        }
    }
}