Cod sursa(job #1409387)

Utilizator alexblackFMI - Dumitrache Alexandru alexblack Data 30 martie 2015 15:03:30
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <unordered_set>
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in ("biconex.in");
ofstream out("biconex.out");
struct leg{int x,y;};
int const N=100005;
unordered_set<int> comp[N];
int niv[N],nic[N];
vector<int> v[N];
stack<leg> stk;
bool viz[N];
int n,m,nr;
void citire()
{
    int a,b;
    in>>n>>m;
    for(int i=1;i<=m;i++)
    {
        in>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
}
inline int min(int x, int y)
{
    if(x<y) return x;
    return y;
}
void dfs(int x)
{
    viz[x]=true;
    size_t dim=v[x].size();
    for(size_t i=0;i<dim;i++)
    {
        int dest=v[x][i];
        if(!viz[dest])
        {
            leg crt;
            crt.x=x;
            crt.y=dest;
            stk.push(crt);
            nic[dest]=niv[dest]=niv[x]+1;
            dfs(dest);
            nic[x]=min(nic[x],nic[dest]);
            if(nic[dest]>=niv[x])
            {
                int iesiri=0;
                do
                {
                    crt=stk.top();
                    stk.pop();
                    iesiri++;
                    comp[nr].insert(crt.x);
                    comp[nr].insert(crt.y);

                }while(!((crt.x==x&&crt.y==dest)||(crt.x==dest&&crt.y==x)));
                nr++;
            }
        }
        else
            if (niv[j]<nic[i] && niv[j]!=niv[i]-1)
        //if((viz[dest])&&(niv[dest]<niv[x]-1))
            nic[x]=niv[dest];
    }
}
void afis()
{
    out<<nr<<"\n";
    for(int i=0;i<nr;i++)
    {
        for(auto itr=comp[i].begin();itr!=comp[i].end();itr++)
            out<<*itr<<" ";
        out<<"\n";
    }
}
int main()
{
    citire();
    //for(int i=1;i<=n;i++)
      //  if(!viz[i])
            dfs(1);
    afis();
    return 0;
}