Cod sursa(job #2498101)

Utilizator redstonegamer22Andrei Ion redstonegamer22 Data 23 noiembrie 2019 14:52:10
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>

using namespace std;

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

vector< int > g[100005];
int index[100005], lowlink[100005], onst[100005];
int ind;

stack< int > st;

vector< int > ctc[100005];
int cnt = 0;

void strongconnect(int v) {
    index[v] = ind;
    lowlink[v] = ind;
    ind++;

    st.push(v);
    onst[v] = 1;

    for(int i = 0; i < g[v].size(); i++) {
        int w = g[v][i];
        if(index[w] == -1) {
            strongconnect(w);
            lowlink[v] = min(lowlink[v], lowlink[w]);
        }
        else if(onst[w] == 1) {
            lowlink[v] = min(lowlink[v], index[w]);
        }
    }

    if(lowlink[v] == index[v]) {
        while(st.top() != v) {
            ctc[cnt].push_back(st.top());
            onst[st.top()] = 0;
            st.pop();
        }
        ctc[cnt].push_back(v);
        onst[v] = 0;
        st.pop();
        cnt++;
    }

}

int main()
{
    int n, m, x, y; in >> n >> m;
    for(int i = 0; i < m; i++) {
        in >> x >> y;
        g[x].push_back(y);
    }

    for(int i = 0; i <= n; i++){
        index[i] = -1;
    }

    ind = 0;
    for(int i = 1; i <= n; i++) {
        if(index[i] == -1)
            strongconnect(i);
    }

    out << cnt << endl;
    for(int i = 0; i < cnt; i++) {
        for(int j = 0; j < ctc[i].size(); j++) {
            out << ctc[i][j] << " ";
        }
        out << endl;
    }

    return 0;
}