Cod sursa(job #2722161)

Utilizator robert.barbu27robert barbu robert.barbu27 Data 12 martie 2021 17:02:35
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define INF 2e9
#define NMAX 150005
#define PMAX 3500
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int n,m,cnt=0,index[100005],low_link[100005],ctc;
vector<int> adj[100005],sol[100005];
bool viz[100005],instack[100005];
stack<int> s;
void dfs(int node)
{
    s.push(node);
    instack[node]=1;
    index[node]=low_link[node]=++cnt;
    for(int i=0; i<adj[node].size(); i++)
    {
        int vec=adj[node][i];
        if(index[vec]==0)
        {
            dfs(vec);
        }
        if(instack[vec]==1)
        {
            low_link[node]=min(low_link[node],low_link[vec]);
        }
    }
    if(index[node]==low_link[node])
    {
        ctc++;
        int x=node;
        do
        {
            x=s.top();
            low_link[x]=low_link[node];
            sol[ctc].pb(x);
            s.pop();
            instack[x]=0;

        }
        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(index[i]==0)
        {
            dfs(i);
        }
    }
    g<<ctc<<'\n';
    for(int i=1;i<=ctc;i++)
    {
        for(int j=0;j<sol[i].size();j++)
        {
            g<<sol[i][j]<<" ";
        }
        g<<'\n';
    }









}