Cod sursa(job #3167361)

Utilizator samyro14Samy Dragos samyro14 Data 10 noiembrie 2023 17:51:05
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include <bits/stdc++.h>
using namespace  std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");
const int maxn = 1e5 + 2;
const int maxm = 2e5 + 2;
const int mod = 666013;
#define ll  long long

int n, m, k;
vector<int> a[maxn + 2], b[maxn + 2], ctc[maxn];
bool visited[maxn + 2];
stack<int> s;
void read(){
    fin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int x, y; fin >> x >> y;
        a[x].push_back(y);
        b[y].push_back(x);
    }

}
void dfs1(int i){
    visited[i] = true;
    for(auto x : a[i])
        if(!visited[x])
            dfs1(x);
    s.push(i);
}
void dfs2(int i, int k){
    visited[i] = true;
    ctc[k].push_back(i);
    for(auto x : b[i])
        if(!visited[x])
            dfs2(x, k);
}
void solve(){ 
    for(int i = 1; i <=n; ++i){
        if(!visited[i])
            dfs1(i);
    }
    for(int i = 1; i <= n; ++i)
        visited[i] = false;
    while(!s.empty()){
        if(!visited[s.top()]){
            k++;
            dfs2(s.top(), k);
        }
        s.pop();
    }

}
void display(){
    fout << k << "\n";
    for(int i = 1; i <= k; ++i){
        for(auto x : ctc[i])
            fout << x << " ";
        fout << "\n";
    }
}
int main(){
    read();
    solve();
    display();
    return 0;
}
/*




*/