Cod sursa(job #1399039)

Utilizator rootsroots1 roots Data 24 martie 2015 15:31:46
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.9 kb
#include <fstream>
#include <vector>
#include <stack>
#include <cstring>

#define MAXV 100001

using namespace std;

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

int V, A;
vector <int> G[MAXV];
vector <vector <int>> scc;
int value[MAXV];
int lowlink[MAXV];
stack <int> st;
int currentValue = 1;
bool inStack[MAXV];

inline void readAndBuild() {
    in >> V >> A;
    
    int x, y;
    for (int a = 0; a < A; ++ a) {
        in >> x >> y;
        
        G[x].push_back(y);
    }
}

inline void dfs(int node) {
    st.push(node);
    inStack[node] = true;
    
    value[node] = currentValue;
    lowlink[node] = currentValue;
    
    currentValue ++;
    
    
    for (vector <int>::iterator it = G[node].begin(); it != G[node].end(); ++ it) {
        if (value[*it] == 0) {
            dfs(*it);
            
            lowlink[node] = min(lowlink[node], lowlink[*it]);
        } else if (inStack[*it]) {
            lowlink[node] = min(lowlink[node], value[*it]);
        }
    }
    
    if (value[node] == lowlink[node]) {
        vector <int> newScc;
        int x;
        
        do {
            x = st.top();
            st.pop();
            inStack[x] = false;
            
            newScc.push_back(x);
        } while (x != node);
        
        scc.push_back(newScc);
    }
}

inline void stronglyConnectedComponentsWithTarjan() {
    memset(inStack, false, sizeof(inStack));
    
    for (int i = 1; i <= V; ++ i) {
        if (value[i] == 0) {
            dfs(i);
        }
    }
}

inline void printResult() {
    out << scc.size() << '\n';
    
    for (vector <vector <int>>::iterator it = scc.begin(); it != scc.end(); ++ it) {
        for (vector <int>::iterator jt = (*it).begin(); jt != (*it).end(); ++ jt) {
            out << *jt << ' ';
        }
        
        out << '\n';
    }
}

int main() {
    readAndBuild();
    stronglyConnectedComponentsWithTarjan();
    printResult();
    
    return 0;
}