Cod sursa(job #2209284)

Utilizator silviu982001Borsan Silviu silviu982001 Data 2 iunie 2018 16:24:52
Problema Componente tare conexe Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;

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

#define NMAX 100005
vector<vector<int> > sol;
vector<int> G[NMAX];

int comp[NMAX];
int level[NMAX];
stack<int> st;
bool inStack[NMAX];
int n, m, x, y;
int indexi;

void dfs(int node){
    comp[node] = ++indexi;
    level[node] = indexi;
    inStack[node] = true;
    st.push(node);
    indexi++;
    
    for(auto next : G[node]){
        if(!comp[next]) dfs(next), level[node] = min(level[node], level[next]);
        else if(inStack[next])  level[node] = min(level[node], level[next]);
    }
    
    if(comp[node] == level[node]){
        sol.push_back(vector<int>());
        
        int v;
        do{
            v = st.top();
            sol[sol.size() - 1].push_back(v);
            inStack[v] = false;
            st.pop();
        }while(v != node);
    }
}

int main()
{
    fin >> n >> m;
    
    for(int i = 1; i <= m; i++){
        fin >> x >> y;
        G[x].push_back(y);
    }
    
    for(int i = 1; i <= n; i++){
        if(comp[i] == 0)
            dfs(i);
    }
    
    fout << sol.size()<< '\n';
    
    for(int i = 0; i < sol.size(); i++){
        for(int j = 0; j < sol[i].size(); j++){
            fout << sol[i][j] << " ";
        }
        
        fout << endl;
    }
    return 0;
}