Cod sursa(job #3243144)

Utilizator CReaper1116Shang Cheng Lin CReaper1116 Data 16 septembrie 2024 08:56:14
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int N = 1e5;
vector <int> e[N];
vector <int> r[N];
bool vis[N];
vector <int> ord1;
vector <int> ord2[N];
int cnt = 0;
void dfs(int node){
    vis[node] = 1;
    for(auto i:r[node]){
        if(!vis[i])dfs(i);
    }
    ord1.push_back(node);
}
void dfs2(int node){
    vis[node] = 0;
    for(auto i:e[node]){
        if(vis[i])dfs2(i);
    }
    ord2[cnt].push_back(node);
}
int main(){
    int n,m;
    fin>>n>>m;
    for(int i = 0;i < m;i++){
        int u,w;
        fin>>u>>w;
        u--;w--;
        e[u].push_back(w);
        r[w].push_back(u);
    }
    for(int i = 0;i < n;i++){
        if(!vis[i]){
            dfs(i);
        }
    }
    reverse(ord1.begin(),ord1.end());
    for(auto i:ord1){
        if(vis[i])dfs2(i),cnt++;
    }
    fout<<cnt<<'\n';
    for(int i = 0;i < cnt;i++){
        for(auto j:ord2[i]){
            fout<<j + 1<<' ';
        }
        fout<<'\n';
    }
    return 0;
}