Cod sursa(job #3256596)

Utilizator Antonio_BiscoveanuAntonio Biscoveanu Antonio_Biscoveanu Data 15 noiembrie 2024 12:04:34
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 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]]==0)
            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;
        do{
            v=stiva.top();
            ps[v]=0;
            stiva.pop();
            sol[nrctc].push_back(v);
        }while(v!=u);
        nrctc++;
    }

    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]==0)
            tarjan(i, i);
    fout<<nrctc<<"\n";
    for(int i=0; i<nrctc; i++)
    {
        //cout<<i<<":  ";
        for(int j=0; j<sol[i].size(); j++)
            fout<<sol[i][j]<<" ";
        fout<<"\n";
    }
}