Cod sursa(job #1387932)

Utilizator sulzandreiandrei sulzandrei Data 14 martie 2015 21:21:47
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <unordered_set>
#include <stack>
#define min(a,b) ((a<b)?a:b)
using namespace std;
ifstream in("bi.in");
ofstream out("bi.out");
vector <int> v[100003];
struct ele{
int x,y;
}edge;
unordered_set<int> ms[100004];
stack <struct ele> s;
bool pcrt[100004];
int niv[100004],nic[100004],nr=0,spa=0,start;
bool viz[100004];
void DFS(int i)
{
    int j;
    for(auto it = v[i].begin();it!=v[i].end();++it)
    {
        j = *it;
        if(viz[j]==0)
        {
            edge.x =i;
            edge.y = j;
            s.push(edge);
            viz[j] = 1;
            if (i==start)
            {
                spa++;
            }
            niv[j]=niv[i]+1; nic[j]=niv[j];
            DFS(j);
            nic[i]=min(nic[j],nic[i]);
            /*if (nic[j]>niv[i])
            {
                mcrt[mi].x = i;              //Aici verificam daca o muchie e critica si pct critice
                mcrt[mi].y = j;
                mi++;
            }
            if(nic[j]>=niv[i] && i!=start)
                pcrt[i] = true;*/
            if (nic[j]>=niv[i])
            {
                do
                {
                    edge = s.top();
                    s.pop();
                    ms[nr].insert(edge.x);
                    ms[nr].insert(edge.y);
                }
                while(!((edge.x==i &&edge.y==j) ||(edge.x==j &&edge.y==i)));
                nr++;
            }
        }
        else
            if (niv[j]<nic[i] && niv[j]!=niv[i]-1)
                nic[i] = niv[j];
    }
}
int main()
{
    int n,m,i,x,y;
    in>>n>>m;
    for(i=1;i<=n;i++)
    {
        viz[i]=false;
        pcrt[i]= false;
    }
    for(i=0;i<m;i++)
    {
        in>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    start = 8;
    niv[start]=1;
    nic[start]=1;
    viz[start]=1;
    DFS(start);
    out<<nr<<"\n";
    for(i=0;i<nr;i++)
    {
        for(auto ite = ms[i].begin();ite!=ms[i].end();ite++)
            out<<*ite<<" ";
        out<<"\n";
    }
    /*if (spa>1)
        pcrt[start]= true;
    for(i=1;i<=n;i++)
       if(pcrt[i])
            out<<i<<" ";
    out<<"\n";
    for(i=0;i<mi;i++)
        out<<mcrt[i].x<<" "<<mcrt[i].y<<"\n";*/
    return 0;
}