Cod sursa(job #2525922)

Utilizator rd211Dinucu David rd211 Data 18 ianuarie 2020 00:29:12
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 100010;
vector<int> graf[NMAX];
int lowlink[NMAX];
int ids[NMAX];
bool inStack[NMAX];
vector<vector<int>> components;
stack<int> stac;
int currentId = 1;
void dfs(int node)
{
    stac.push(node);
    inStack[node] = true;
    ids[node] = currentId++;
    lowlink[node] = ids[node];
    for(int friendly : graf[node])
    {
        if(ids[friendly]==0)
            dfs(friendly);
        if(inStack[friendly])
            lowlink[node] = min(lowlink[node], lowlink[friendly]);
    }
    if(ids[node]==lowlink[node])
    {
        vector<int> component;
        while(stac.top()!=node) {
                lowlink[stac.top()]=lowlink[node];
                inStack[stac.top()] = false;
                component.push_back(stac.top());
                stac.pop();
        }
        component.push_back(stac.top());
        inStack[stac.top()] = false;
        stac.pop();
        components.push_back(component);
    }
}
int n, m;
int main()
{
    fin>>n>>m;
    while(m--)
    {
        int x, y;
        fin>>x>>y;
        graf[x].push_back(y);
    }
    for(int i= 1;i<=n;i++)
    {
        if(ids[i]==0) dfs(i);
    }
    fout<<components.size()<<"\n";
    for(auto v:components)
    {
        for(auto x:v)
            fout<<x<<" ";
        fout<<'\n';
    }
    return 0;
}