Cod sursa(job #3373818)

Utilizator TintsooTint Sabei Soe Win Tintsoo Data 7 noiembrie 2026 22:33:39
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm> 
#include <stack> 

using namespace std; 

vector<int> adj[100005], adjT[100005];
stack<int> st; 
bool visited[100005];
vector<vector<int>> SCC; 

int n, m; 

void dfs(int u){

    visited[u] = true; 

    for (int v : adj[u]){
        if (!visited[v]){
            dfs(v); 
        }
    }

    st.push(u); 
}


void dfsT(int u, vector<int>& group){

    visited[u] = true; 
    group.push_back(u); 
    
    for (int v : adjT[u]){
        if (!visited[v]){
            dfsT(v, group); 
        }
    }

}



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

    fin >> n >> m; 

    for (int i = 0; i < m; i++){
        int u, v; 
        fin >> u >> v; 

        adj[u].push_back(v); 
        adjT[v].push_back(u); 

    }

    for (int i = 1; i <= n; i++){
        if (!visited[i]){
            dfs(i); 
        }
    }

    fill(visited + 1, visited + n + 1, false); 


    int sccCount = 0; 
    while (!st.empty()){
        int u = st.top(); 
        st.pop(); 

        if (!visited[u]){
            vector<int> group; 
            sccCount++; 
            dfsT(u, group); 
            SCC.push_back(group); 
        }
    }


    for (int i = 0; i < sccCount; i++){
        sort(SCC[i].begin(), SCC[i].end()); 
    }
    

    fout << sccCount << endl; 

    for (auto g : SCC){
        for (int i : g){
            fout << i << " ";
        }
        fout << endl; 
    }

    return 0; 

}