Cod sursa(job #3278380)

Utilizator iustincmbMaican Iustin iustincmb Data 19 februarie 2025 16:55:03
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>
using namespace std;
vector<int>adj[100005];
vector<int>adj1[100005];
vector<int>v;
vector<int>ver[100005];
bool vis[100005];
void dfs(int node){
    vis[node]=1;
    for(auto i : adj[node]){
        if(vis[i]==0)
            dfs(i);
    }
    v.push_back(node);
}
void dfs1(int node, int u){
    vis[node]=1;
    ver[u].push_back(node);
    for(auto i : adj1[node]){
        if(vis[i]==0)
            dfs1(i, u);
    }
}
int main(){
    ifstream cin ("ctc.in");
    ofstream cout ("ctc.out");
    int n, m, a, b;
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        cin >> a >> b;
        adj[a].push_back(b);
        adj1[b].push_back(a);
    }
    for(int i=1; i<=n; i++){
        if(vis[i]==0)
            dfs(i);
    }
    for(int i=1; i<=n; i++)
        vis[i]=0;
    reverse(v.begin(), v.end());
    int cnt=0;
    for(int i=0; i<v.size(); i++){
        if(vis[v[i]]==0){
            cnt++;
            dfs1(v[i], cnt);
        }
    }
    cout << cnt << '\n';
    for(int i=1; i<=cnt; i++){
        for(int j=0; j<ver[i].size(); j++)
            cout << ver[i][j] << ' ';
        cout << '\n';
    }
    return 0;
}