Cod sursa(job #2537898)

Utilizator denmirceaBrasoveanu Mircea denmircea Data 4 februarie 2020 08:16:47
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <iostream>
#define dim 100005
#include <deque>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int g,low[dim],niv[dim],ctc,n,m,x,y,i,j;
bitset<dim> IQ;
deque<int> q;
vector <int> L[dim],C[dim];
void dfs(int nod)
{
    g++;
    low[nod]=g;
    niv[nod]=g;
    IQ[nod]=1;
    q.push_back(nod);
    for(int i=0; i<L[nod].size(); i++)
    {
        int vecin=L[nod][i];
        if(niv[vecin]==0){
            dfs(vecin);
            low[nod]=min(low[nod],low[vecin]);
        }else if(IQ[nod]==1){
            low[nod]=min(low[nod],low[vecin]);
        }
    }
    if(low[nod]==niv[nod]){
        ctc++;
        do{
            C[ctc].push_back(q.back());
            IQ[q.back()]=0;
            q.pop_back();
        }while(q.back()!=nod);
        C[ctc].push_back(q.back());
        IQ[q.back()]=0;
        //cout<<q.back()<<" ";
    q.pop_back();
    }
}
int main()
{
    fin>>n>>m;
    for(; m--;)
    {
        fin>>x>>y;
        L[x].push_back(y);
    }
    for(i=1; i<=n; i++)
    {
        if(!niv[i])
        {
            dfs(i);
        }
    }
    fout<<ctc<<"\n";
    for(i=1;i<=ctc;i++){
        for(j=0;j<C[i].size();j++)
            fout<<C[i][j]<<" ";
            fout<<"\n";
    }
}