Cod sursa(job #2724727)

Utilizator cyg_SerbanBFlorin Gheorghe cyg_SerbanB Data 17 martie 2021 18:32:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#include <map>
using namespace std;
vector<int> adc[100005];
vector<vector<int> > conx;
bool viz[100005];
int nr[100005],tata[100005],n,m,k;
stack<int> stv;
void dfs(int nod)
{
    nr[nod]=tata[nod]=k++;
    stv.push(nod);
    viz[nod]=1;
    for(int i=0;i<adc[nod].size();++i)
    {
        if(nr[adc[nod][i]]==0)
        {
            dfs(adc[nod][i]);
            if(tata[nod]>tata[adc[nod][i]])
                tata[nod]=tata[adc[nod][i]];
        }
        else
            if(viz[adc[nod][i]] && tata[nod]>tata[adc[nod][i]])
                tata[nod]=tata[adc[nod][i]];
    }
    if(nr[nod]==tata[nod])
    {
        vector<int> aux;
        int x;
        do
        {
            x=stv.top();
            aux.push_back(x);
            viz[x]=0;
            stv.pop();
        }while(x!=nod);
        conx.push_back(aux);
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        adc[x].push_back(y);
    }
    k=1;
    for(int i=1;i<=n;++i)
        if(nr[i]==0)
            dfs(i);
    printf("%d\n",conx.size());
    for(int j=0;j<conx.size();++j)
    {
        for(int i=0;i<conx[j].size();++i)
            printf("%d ",conx[j][i]);
        
        printf("\n");
    }
    return 0;
}