Cod sursa(job #2611131)

Utilizator dragos231456Neghina Dragos dragos231456 Data 6 mai 2020 14:31:58
Problema Componente tare conexe Scor 34
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>
#define node vecini[x][i]
using namespace std;

const int N=100005;

ifstream f("ctc.in");
ofstream g("ctc.out");

int n,m,x,y;
vector<int> vecini[N];
int id[N],low[N],a[N],inq[N],extr[N],s;
int nrctc,nodes[N],ctcsize[N];

void dfs(int x,int k)
{
    low[x]=id[x]=k; inq[x]=1; a[k]=x;
    for(int i=0;i<vecini[x].size();++i)
    {
        if(!id[node])
        {
            dfs(node,k+1);
            low[x]=min(low[x],low[node]);
        }
        else if(inq[node]) low[x]=min(low[x],low[node]);
    }
    //cout<<x<<' '<<id[x]<<' '<<low[x]<<endl;
    extr[++s]=x;
    if(low[x]==id[x])
    {
        nrctc++;
        ctcsize[nrctc]=ctcsize[nrctc-1]+s;
        for(int i=1;i<=s;++i)
        {
            nodes[ctcsize[nrctc-1]+i]=extr[i];
        }
        s=0;
    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i) f>>x>>y, vecini[x].push_back(y);
    for(int i=1;i<=n;++i) if(!id[i])
    {
        s=0;
        dfs(i,1);
    }
    g<<nrctc<<'\n';
    for(int i=1;i<=nrctc;++i)
    {
        for(int j=ctcsize[i-1]+1;j<=ctcsize[i];++j) g<<nodes[j]<<' ';
        g<<'\n';
    }
    return 0;
}