Cod sursa(job #2357402)

Utilizator ciutanpCiuta Andrei Calin ciutanp Data 27 februarie 2019 12:55:15
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include<bits/stdc++.h>
#define NMAX 100001
#define pb push_back
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

vector<int>G[NMAX];
bitset<NMAX>viz;
set<int>sol[NMAX];
stack<int >C;
int h[NMAX],mini[NMAX];
int n,m,soli;

void DFS(int node)
{
    mini[node]=h[node];
    viz[node]=1;
    C.push(node);
    for(auto it:G[node])
    {
        if(viz[it])
        {
            mini[node]=min(mini[node],h[it]);
            continue;
        }
        h[it]=h[node]+1;
        DFS(it);
        mini[node]=min(mini[node],mini[it]);
        if(mini[it]>=h[node])
        {
            soli++;
            sol[soli].insert(node);
            int a;
            do{
                a=C.top();
                C.pop();
                sol[soli].insert(a);
            }while(a!=it);
        }
    }
}

int main()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y;
        f>>x>>y;
        G[x].pb(y);
        G[y].pb(x);
    }
    for(int i=1;i<=n;++i)
        if(!viz[i])
    {
        h[i]=1;
        DFS(i);
    }
    g<<soli<<'\n';
    for(int i=1;i<=soli;++i)
    {
        for(auto it:sol[i])
            g<<it<<' ';
        g<<'\n';
    }

}