Cod sursa(job #2272616)

Utilizator RaduXD1Nicolae Radu RaduXD1 Data 30 octombrie 2018 14:27:11
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>
#include <queue>
#include <cstring>
#define INF 1000000000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int low[100001],niv[100001],d[100001],n,i,j,lvl,a,b,nr,k;
vector<int> s,sol[100001],v[100001];

void dfs(int nod)
{
    int i,vecin;
    low[nod]=++lvl;niv[nod]=lvl;
    d[nod]=1;
    s.push_back(nod);
    for(i=0;i<v[nod].size();i++)
    {
        vecin=v[nod][i];
        if(niv[vecin]&&d[vecin])
                low[nod]=min(low[nod],niv[vecin]);
        if(niv[vecin]==0)
        {
            dfs(vecin);
            low[nod]=min(low[nod],low[vecin]);
        }
    }
    if(niv[nod]==low[nod])
    {
        ++nr;
        for(;s.back()!=nod;){sol[nr].push_back(s.back());d[s.back()]=0;s.pop_back();}
        sol[nr].push_back(s.back());d[s.back()]=0;s.pop_back();
    }
}

int main()
{
    fin>>n>>k;
    for(i=1;i<=k;i++)
    {
        fin>>a>>b;
        v[a].push_back(b);
    }
    for(i=1;i<=n;i++)
        if(niv[i]==0)
            dfs(i);
    fout<<nr<<"\n";
    for(i=1;i<=nr;i++){for(j=0;j<sol[i].size();j++) fout<<sol[i][j]<<" "; fout<<"\n";}
    return 0;
}