Cod sursa(job #2872540)

Utilizator k2y201342asdfadfsafsd k2y20 Data 17 martie 2022 12:40:38
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
using namespace std;

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


const int N=1e5;

struct graf
{
    vector<int> v;
}la[N+5];

stack<int> stk;
int id[N+5],low[N+5];
bool onStk[N+5];
int nrCTC,nrid;
vector<vector<int> >ctc;

void dfs(int nod)
{
    low[nod]=id[nod]=++nrid;
    stk.push(nod);
    onStk[nod]=1;
    
    for(int i=0;i<la[nod].v.size();i++)
    {
        int to=la[nod].v[i];
        
        if(id[to] == -1) dfs(to);
        if(onStk[to]) low[nod]=min(low[to],low[nod]);
    }
    
    if(low[nod] == id[nod])
    {
        vector<int> aux;
        while(stk.top()!=nod)
        {
            aux.push_back(stk.top());
            onStk[stk.top()]=0;
            stk.pop();
        }
        aux.push_back(stk.top());
        onStk[stk.top()]=0;
        stk.pop();
        ctc.push_back(aux);
        nrCTC++;
    }
}

void Tarjan(int n)
{
    for(int i=1;i<=n;i++) id[i]=-1;
    
    for(int i=1;i<=n;i++)
    if(id[i] == -1)
    {
        dfs(i);
    }
}

int main()
{
    int n,m; cin>>n>>m;
    
    for(int i=1;i<=m;i++)
    {
        int x,y; cin>>x>>y;
        la[x].v.push_back(y);
    }
    
    Tarjan(n);
    out<<nrCTC<<'\n';
    for(int i=0;i<ctc.size();i++)
    {
        for(int j=0;j<ctc[i].size();j++)
        out<<ctc[i][j]<<' ';
        out<<'\n';
    }
    return 0;
}