Cod sursa(job #2796514)

Utilizator Teodor_AxinteAxinte Teodor-Ionut Teodor_Axinte Data 8 noiembrie 2021 12:29:00
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
//kosaraju
#include <bits/stdc++.h>

using namespace std;

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

const int N = 100010;

int viz_1[N],viz_2[N];
vector<int> nxt[N], prv[N], ans[N], top;
int n,m, nr_ans;

void dfs_1(int node){
    viz_1[node] = 1;
    for(auto it : nxt[node])
        if(!viz_1[it])
            dfs_1(it);
    top.push_back(node);
}

void dfs_2(int node){
    viz_2[node] = 1;

    ans[nr_ans].push_back(node);

    for(auto it:prv[node])
        if(!viz_2[it])
            dfs_2(it);
}

int main(){
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        nxt[x].push_back(y);
        prv[y].push_back(x);
    }

    for(int i=1;i<=n;i++)
        if(!viz_1[i])
            dfs_1(i);

    reverse(top.begin(),top.end());

    for(auto it:top)
        if(!viz_2[it])
        {
            nr_ans++;
            dfs_2(it);
        }

    fout<<nr_ans;

    for(const auto &it:ans)
    {
        for(auto elem:it)
            fout<<elem<<" ";
        fout<<'\n';
    }

    return 0;
}