Cod sursa(job #2926456)

Utilizator GhiciCineRazvan Dumitriu GhiciCine Data 17 octombrie 2022 19:48:40
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
 
using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");
 
vector<vector<int> >adj;
vector<vector<int> >components;
vector<bool>onStack;
vector<int>idx, lowlink;
 
stack<int>s;
 
int currIdx = 1;
 
void strongConnect(int node) {
    idx[node] = lowlink[node] = currIdx;
    currIdx++;
    s.push(node);
    onStack[node] = true;
    
    for(auto vec: adj[node]) {
        if(idx[vec] == 0) {
            strongConnect(vec);
            lowlink[node] = min(lowlink[node], lowlink[vec]);
        } else if(onStack[vec]) {
            lowlink[node] = min(lowlink[node], idx[vec]);
        }
    }
    
    if(idx[node] == lowlink[node]) {
        vector<int>component;
        int currNode;
        do {
            currNode = s.top();
            s.pop();
            component.push_back(currNode);
            onStack[currNode] = false;
        } while(currNode != node);
        components.push_back(component);
    }
}
 
int main() {
    int n, m, x, y;
    
    fin >> n >> m;
    
    adj.resize(n + 1);
    idx.resize(n + 1, 0);
    lowlink.resize(n + 1, 0);
    onStack.resize(n + 1, false);
    
    for(int i = 0; i < m; i++) {
        fin >> x >> y;
        adj[x - 1].push_back(y - 1);
    }
    
    for(int i = 0; i < n; i++) {
        if(idx[i] == 0) {
            strongConnect(i);
        }
    }
    
    fout << components.size() << "\n";
    for(auto component: components) {
        for(auto node: component) {
            fout << node + 1 << " ";
        }
        fout << "\n";
    }
    return 0;
}