Cod sursa(job #3246618)

Utilizator AlexSerban21Serban Alexandru AlexSerban21 Data 3 octombrie 2024 19:59:33
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
bitset <100001> viz;
vector <int> s,v[100001];
vector <vector <int>> sol;
int n,m,i,j,x,y,k,nr,nrc,stiva[100001],low[100001];
void dfs (int nod,int t)
{
    viz[nod]=1;
    low[nod]=++nr;
    int nrnod=nr;
    stiva[++k]=nod;
    for (int i=0; i<v[nod].size (); i++)
    {
        int vecin=v[nod][i];
        if (!viz[vecin])
            dfs (vecin,nod);
        low[nod]=min (low[nod],low[vecin]);
    }
    if (nrnod==low[nod])
    {
        s.clear ();
        do
        {
            nrc=stiva[k];
            s.push_back (nrc);
            k--;
        }
        while (nrc!=nod);
        sol.push_back (s);
    }
}
int main()
{
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        fin>>x>>y;
        v[x].push_back (y);
    }
    for (i=1; i<=n; i++)
    {
        if (!viz[i])
            dfs (i,0);
    }
    fout<<sol.size ()<<"\n";
    for (i=0; i<sol.size (); i++)
    {
        for (j=0; j<sol[i].size (); j++)
            fout<<sol[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}