Cod sursa(job #2674452)

Utilizator robert.barbu27robert barbu robert.barbu27 Data 19 noiembrie 2020 11:02:48
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define nmax 1000000
#define MMAX 100000
#define inf 1e18
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
vector<int> adj[100005];
int n,m,low_link[100005],idx[100005],cnt=0,ctc=0;
bool viz[100005],instack[100005];
vector<int> sol[100005];
stack<int> s;
void dfs(int node)
{
    s.push(node);
    instack[node]=true;
    idx[node]=low_link[node]=++cnt;
    for(auto x:adj[node])
    {
        if(idx[x]==0) {dfs(x);}
        if(instack[x]==1)
        {
            low_link[node]=min(low_link[node],low_link[x]);
        }
    }
    if(idx[node]==low_link[node])
    {
        ctc++;
        int x=node;
        do
        {
            x=s.top();
            low_link[x]=idx[node];
            sol[ctc].pb(x);
            instack[x]=0;
            s.pop();
        }
        while(x!=node);
    }



}
int main()
{
    f>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        f>>x>>y;
        adj[x].pb(y);
    }
    for(int i=1; i<=n; i++)
    {
        if(idx[i]==0)
        {
            dfs(i);
        }
    }
    g<<ctc<<'\n';
    for(int i=1;i<=ctc;i++)
    {
        for(auto x:sol[i])
        {
            g<<x<<" ";
        }
        g<<'\n';
    }
}