Cod sursa(job #2368460)

Utilizator WayronUrsu Ianis-Vlad Wayron Data 5 martie 2019 16:15:05
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> graph, connected_components;
int n, m;

void read_from_file(){
    ifstream fin("ctc.in");
    fin>>n>>m;

    graph.resize(n+1);

    int x, y;

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

    fin.close();
}

int idx=0, nr_ctc=0;
vector<int> low_link, id;
vector<bool> inStack, visited;
stack<int> Stack;


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

    for(auto& kid:graph.at(node)){
        if(id.at(kid)==false) Tarjan(kid);

        if(inStack.at(kid)==true){
            low_link.at(node) = min(low_link.at(node), low_link.at(kid));
        }

    }

    if(low_link.at(node)==id.at(node)){
            nr_ctc++;
            vector<int> component;
            int x;

            do{
                component.push_back(x = Stack.top());
                inStack.at(x) = false;
                Stack.pop();
            } while(x!=node);

            connected_components.push_back(component);
    }
}

void print_to_file(){
    ofstream fout("ctc.out");

    fout<<nr_ctc<<endl;

    for(auto& component:connected_components){
        for(auto& node:component) fout<<node<<" ";

        fout<<endl;
    }
}

int main()
{
    read_from_file();

    low_link.resize(n+1);
    inStack.resize(n+1, false);
    id.resize(n+1);

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

    print_to_file();
}