Cod sursa(job #2205213)

Utilizator GeorgeCalinPetruta George-Calin GeorgeCalin Data 18 mai 2018 12:21:12
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>
#include <stack>
#define nmax 100002
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");

vector <int> g[nmax];
vector <int> sol[nmax];
stack <int> st;
int low[nmax],v[nmax],t[nmax],viz[nmax],x,n,m,c=0,y;


void dfs(int nod)
{
    viz[nod]=1;
    v[nod]=v[t[nod]]+1;
    low[nod]=v[nod];
    st.push(nod);
    for(int i=0;i<g[nod].size();i++)
    {
        int k=g[nod][i];
        if(viz[k])
        {
            if(k!=t[nod])
                low[nod]=min(low[nod],v[k]);
            continue;
        }
        t[k]=nod;
        dfs(k);
        low[nod]=min(low[nod],low[k]);
        if(low[k]>=v[nod])
        {
            int x;
            c++;
            do
            {
                x=st.top();
                st.pop();
                sol[c].push_back(x);
            }while(k!=x);
            sol[c].push_back(nod);
        }
    }
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
        {
            t[i]=0;
            dfs(i);
        }
    fout<<c<<"\n";
    for(int i=1;i<=c;i++){
        for(int j=0;j<sol[i].size();j++)
            fout<<sol[i][j]<<" ";
        fout<<"\n";
    }
    return 0;
}