Cod sursa(job #2574740)

Utilizator victorzarzuZarzu Victor victorzarzu Data 6 martie 2020 09:32:58
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n, m, x, y;
vector<int> graf[100005];
vector<int> componente[100005];
int dfn[100005];
int low[100005];
bool viz[100005];
stack<int> s;
int nr;

void Read()
{
    f>>n>>m;
    for(int i = 1;i <= m;++i)
    {
        f>>x>>y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }
}

void dfs(int nod, int parinte, int nivel)
{
    viz[nod] = true;
    dfn[nod] = low[nod] = nivel;
    s.push(nod);
    for(vector<int>::iterator it = graf[nod].begin();it != graf[nod].end();++it)
    {
        if(viz[*it])
            low[nod] = min(low[nod], dfn[*it]);
        else
        {
            dfs(*it, nod, nivel + 1);
            low[nod] = min(low[nod], low[*it]);
            if(low[*it] >= dfn[nod])
            {
                int x;
                ++nr;
                componente[nr].push_back(nod);
                do{
                    x = s.top();
                    s.pop();
                    componente[nr].push_back(x);
                }while(x != *it);
            }
        }
    }
}

void Print()
{
    g<<nr<<'\n';
    for(int i = 1;i <= n;++i)
    {
        for(vector<int>::iterator it = componente[i].begin();it != componente[i].end();++it)
            g<<*it<<" ";
        g<<'\n';
    }

}

int main()
{
    Read();
    dfs(1, -1, 1);
    Print();
    return 0;
}