Cod sursa(job #1506712)

Utilizator adina0822Ciubotaru Adina-Maria adina0822 Data 20 octombrie 2015 21:55:59
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.7 kb
using namespace std;
#include <fstream>
#include <set>
#include <stack>
#include <vector>
#include <algorithm>
#define Maxn 100005
#define Min(a,b)((a)<(b)? (a):(b))

ifstream f ("biconex.in");
ofstream g ("biconex.out");

vector<int> adj[Maxn],dfn,low;
vector<vector<int> >C;
stack < pair < int,int > >stk;

void read (int &n)
{
    int m,x,y;
    f>>n>>m;
    while(m--)
    {
        f>>x>>y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
}

void cache_bc(int x,int y)
{
    vector<int> con;
    int tx,ty;
    do
    {
        tx=stk.top().first;
        ty=stk.top().second;
        stk.pop();
        con.push_back(tx);
        con.push_back(ty);
    }
    while(tx!=x || ty!=y);
    C.push_back(con);
}

void DF(int n, int fn, int number)
{
    vector<int>::iterator it;
    dfn[n]=low[n]=number;
    for(it=adj[n].begin(); it!=adj[n].end(); it++)
    {
        if(*it==fn) continue;
        if(dfn[*it]==-1)
        {
            stk.push(make_pair(n,*it));
            DF(*it,n,number+1);
            low[n]=Min(low[n],low[*it]);
            if(low[*it]>=dfn[n]) //n e punct de articulatie
              cache_bc(n,*it);
        }
        else low[n]=Min(low[n],dfn[*it]); //[n,*it] e muchie de intoarcere de la n la *it
    }
}

int main()
{
    int n;
    read(n);
    dfn.resize(n+1);
    dfn.assign(n+1,-1);
    low.resize(n+1);
    DF(1,0,0);
    g<<C.size()<<'\n';
    for(size_t i=0; i<C.size(); i++)
    {
        sort(C[i].begin(),C[i].end());
        C[i].erase(unique(C[i].begin(),C[i].end()),C[i].end());
        for(size_t j=0; j<C[i].size(); j++)
           g<<C[i][j]<<" ";
        g<<'\n';

    }

  return 0;
}