Cod sursa(job #2375360)

Utilizator WayronUrsu Ianis-Vlad Wayron Data 8 martie 2019 08:19:31
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n, m;

vector<vector<int>> ctcs;
vector<vector<int>> graph = vector<vector<int>>(NMAX, vector<int>());
vector<int> low = vector<int>(NMAX);
vector<int> id = vector<int>(NMAX, -1);
vector<bool> inStack = vector<bool>(NMAX, false);
stack<int> st;

int idx = 0;    int nr_ctc = 0;

void Tarjan(int node){
    id.at(node) = low.at(node) = ++idx;
    st.push(node);
    inStack.at(node) = true;

    for(auto& elem:graph.at(node)){
        if(id.at(elem)==-1) Tarjan(elem);

        if(inStack.at(elem)==true) low.at(node) = min(low.at(node), low.at(elem));
    }

    if(low.at(node)==id.at(node)){
        int ctc_node;
        vector<int> ctc;

        do{
            ctc_node = st.top();
            st.pop();
            ctc.push_back(ctc_node);
            inStack.at(ctc_node) = false;

        } while(ctc_node!=node);

        ctcs.push_back(ctc);    nr_ctc++;
    }
}


int main()
{
    fin>>n>>m;

    int x, y;
    for(int i=1; i<=m; i++){
        fin>>x>>y;
        graph.at(x).push_back(y);
    }

    for(int i=1; i<=n; i++)
        if(id.at(i)==-1) Tarjan(i);

    fout<<nr_ctc<<"\n";

    for(auto& ctc:ctcs){
        for(auto& ctc_node:ctc) fout<<ctc_node<<" ";
        fout<<"\n";
    }



}