Cod sursa(job #2611146)

Utilizator dragos231456Neghina Dragos dragos231456 Data 6 mai 2020 14:56:12
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 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],k,inq[N],s;
int nrctc,nodes[N],ctcsize[N];

void dfs(int x)
{
    ++k; ++s;
    low[x]=id[x]=k; a[s]=x; inq[x]=1;
    for(int i=0;i<vecini[x].size();++i)
    {
        if(!id[node])
        {
            dfs(node);
            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;
    if(low[x]==id[x])
    {
        nrctc++;
        ctcsize[nrctc]=ctcsize[nrctc-1];
        while(inq[x]==1)
        {
            inq[a[s]]=0;
            ctcsize[nrctc]++;
            nodes[ctcsize[nrctc]]=a[s];
            --s;
        }
    }
}

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])
    {
        k=0; s=0;
        dfs(i);
    }
    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;
}