Cod sursa(job #2234030)

Utilizator BiancaMariaVulsanVulsan Bianca Maria BiancaMariaVulsan Data 25 august 2018 10:18:34
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m, d[100002], l[100002], tata[100002], nr;
vector <int> v[100002], ans[100002];
deque <int> s;

void citire()
{
    int i,j,k;
    f>>n>>m;
    for(k=1; k<=m; k++)
    {
        f>>i>>j;
        v[i].push_back(j);
        v[j].push_back(i);
    }
}

void dfs(int nod)
{
    int i,k, next;
    d[nod]=d[tata[nod]]+1;
    l[nod]=d[nod];
    s.push_front(nod);
    for(i=0; i<v[nod].size(); i++)
    {next=v[nod][i];
        if(!d[next])
        {
            tata[next]=nod;
            dfs(next);
            l[nod]=min(l[next], l[nod]);
            if(l[next]>=d[nod])
            {
                do
                {
                    k=s[0];
                    s.pop_front();
                    ans[nr].push_back(k);
                }while(next!=k);
                ans[nr].push_back(nod);
                nr++;
            }
        }
        else
            if(next!=tata[nod])
            l[nod]=min(l[nod], d[next]);
    }
}

int main()
{
    int i,j;
    citire();
    for(i=1; i<=n; i++)
        if(!d[i])
        {tata[i]=0; dfs(i);}
    g<<nr<<endl;
    for(i=0; i<nr; i++)
        {for(j=0; j<ans[i].size(); j++)
            g<<ans[i][j]<<" ";
        g<<endl;}
    f.close();
    g.close();
    return 0;
}