Cod sursa(job #3256519)

Utilizator Antonio_BiscoveanuAntonio Biscoveanu Antonio_Biscoveanu Data 14 noiembrie 2024 19:39:47
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include<bits/stdc++.h>
#define inf 1000005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, m, ss, ps[100005], d[100005], nrctc;
vector<int> l[100005], sol[100005];
stack<int> stiva;

int tarjan(int u, int depth)
{
    d[u]=depth;
    ps[u]=1;
    stiva.push(u);
    for(int i=0; i<l[u].size(); i++)
    {
        if(d[l[u][i]]==inf)
            d[u]=min(d[u], tarjan(l[u][i], depth+1));
        else if(ps[l[u][i]]==1)
            d[u]=min(d[u], d[l[u][i]]);
    }

    if(d[u]==depth)
    {
        int v;
        nrctc++;
        do{
            v=stiva.top();
            ps[v]=0;
            stiva.pop();
            sol[nrctc].push_back(v);
        }while(v!=u);

    }

    return d[u];
}

int main()
{
    fin>>n>>m;
    while(m)
    {
        int x,y;
        fin>>x>>y;
        l[x].push_back(y);
        m--;
    }
    for(int i=1; i<=n; i++)
        d[i]=inf;
    for(int i=1; i<=n; i++)
        if(d[i]==inf)
            tarjan(i, i);
    fout<<nrctc<<"\n";
    for(int i=1; i<=nrctc; i++)
    {
        //cout<<i<<":  ";
        for(int j=0; j<sol[i].size(); j++)
            fout<<sol[i][j]<<" ";
        fout<<"\n";
    }
}