Cod sursa(job #3229401)

Utilizator cret007Andrei Cret cret007 Data 15 mai 2024 20:59:39
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <bits/stdc++.h>

using namespace std;
#define MAX_NODE 100005

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

vector <vector <int>> solutions;
vector <bool> inStack (MAX_NODE, false);
stack <int> Stack;
vector <vector <int>> adj(MAX_NODE);
vector <int> parent (MAX_NODE, -1);
vector <int> low_link(MAX_NODE, -1);
vector <int> discover(MAX_NODE, -1);
int timestamp = 0;


void dfs(int i) {

    discover[i] = low_link[i] = ++timestamp;
    Stack.push(i);
    inStack[i] = true;

    for (int neigh: adj[i]) {
        if (parent[neigh] == -1) {
            parent[neigh] = i;
            dfs(neigh);
            low_link[i] = min(low_link[i], low_link[neigh]);
        } else if (inStack[neigh]) {
            low_link[i] = min(low_link[i], low_link[neigh]);
        }
    }

    if (discover[i] == low_link[i]) {
        vector<int>scc;
        int x;

        do {
            auto x = Stack.top();
            Stack.pop();
            inStack[x] = false;
            scc.push_back(x);
        }while (i != scc.back());

        solutions.push_back(scc);
        
    }
    /*
    if(found[node]==low_link[node]){
            vector<int>new_scc;
            do{
                auto x = nodes_stack.top();
                nodes_stack.pop();
                in_stack[x]=false;
                new_scc.push_back(x);
            } while(node!=new_scc.back());
            all_sccs.push_back(new_scc);
        }*/
}

 void print_output() {

        fout << solutions.size() << '\n';
        for (const auto& scc : solutions) {
            for (auto node : scc) {
                fout << node << ' ';
            }
            fout << '\n';
        }
        fout.close();
    }


int main() {

    int nodes, edges, x, y;

    fin>>nodes>>edges;

    for (int i = 0; i < edges; i++) {
        fin>>x>>y;
        adj[x].push_back(y);
    }


    int time = 0;

    for (int i = 1; i <= nodes; i++) {
        if (parent[i] == -1) {
            parent[i] = i;
            dfs(i);  
        }
    }

    print_output();

    return 0;
}