Cod sursa(job #1676527)

Utilizator elevenstrArina Raileanu elevenstr Data 5 aprilie 2016 23:05:25
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
#define MAX 100008
vector <int> v[MAX],sol[MAX];
int n,m,a,b,lvl[MAX],low[MAX],c;
stack <pair<int, int> > S;
void dfs(int nod,int lev,int tt)
{
    lvl[nod]=low[nod]=lev;
    for(int i=0;i<v[nod].size();i++)
    {
        int nxt=v[nod][i];
        if(nxt==tt)continue;
        if(!low[nxt])
        {   S.push({nod,nxt});
            dfs(nxt,lev+1,nod);
            low[nod]=min(low[nod],low[nxt]);
            if(low[nxt]>=lvl[nod])
            {     ++c;
                  sol[c].push_back(nod);
                while(!S.empty()&&(S.top().first!=nod||S.top().second!=nxt))
                {
                    sol[c].push_back(S.top().second);
                    S.pop();
                }
                sol[c].push_back(S.top().second);
                    S.pop();
            }
        }
        else
            low[nod]=min(low[nod],lvl[nxt]);
        }

}
int main()
{
     in>>n>>m;
     while(m--)
     {
         in>>a>>b;
         v[a].push_back(b);
         v[b].push_back(a);
     }
     dfs(1,1,-1);
   out<<c<<'\n';
   for(int i=1;i<=c;i++)
   {
       for(int j=0;j<sol[i].size();j++)
        out<<sol[i][j]<<" ";
       out<<'\n';
   }
    return 0;
}