Cod sursa(job #2215438)

Utilizator Anastasia11Susciuc Anastasia Anastasia11 Data 22 iunie 2018 10:23:39
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <vector>
#define Nmax 100005

using namespace std;

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

vector <int> v[Nmax], sol[Nmax];
vector <int> ::iterator it;
int n, m, ans;
bool seen[Nmax];
int x, y, num_comp;
int st[Nmax], top;
int lv[Nmax], lmax[Nmax];

void GetComponent(int x, int dd)
{
    sol[num_comp].push_back(dd);
    while(st[top] != x && top >= 1)
    {
        sol[num_comp].push_back(st[top]);
        top--;
    }
    if (top > 0)
    {
        sol[num_comp].push_back(x);
        top--;
    }
}

void dfs(int x, int dd)
{
    seen[x]=true;
    lmax[x]=lv[x]=lv[dd]+1;
    for ( int i = 0, l=v[x].size(); i<l; i ++ )
    {
        int y=v[x][i];
        if(y == dd) continue;
        if(seen[y] == true)
        {
            lmax[x]=min(lmax[x], lv[y]);
            continue;
        }
        st[++top]=y;
        dfs(y, x);
        lmax[x]=min(lmax[x], lmax[y]);
        if(lv[x] <= lmax[y] )
        {
            num_comp++;
            GetComponent(y, x);
        }
    }
}

int main()
{
    f >> n >> m;
    for ( int i = 1; i <= m; i ++ )
    {
        f >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for ( int i = 1; i <= n; i ++ )
        if(seen[i] == false)
        dfs(i,0);
    g << num_comp << '\n';
    for ( int i = 1; i <= num_comp; i ++ )
    {
        for ( it=sol[i].begin(); it != sol[i].end(); it ++ )
            g << *it << " ";

        g << '\n';
    }

}