Cod sursa(job #1014429)

Utilizator misinozzz zzz misino Data 22 octombrie 2013 18:23:07
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include<fstream>
#include<vector>
#include<algorithm>
#define N 100010
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int i,n,j,x,y,nr,m,viz[N],mini[N],niv[N],t[N];
vector<int>sol[N],v[N];
vector<pair<int,int> >vec;
inline void adauga(int x,int y)
{
    ++nr;
    sol[nr].push_back(x),sol[nr].push_back(y);
    while((x!=vec.back().first||y!=vec.back().second)&&(x!=vec.back().second||y!=vec.back().first))
    {
        sol[nr].push_back(vec.back().first);
        sol[nr].push_back(vec.back().second);
        vec.pop_back();
    }
    vec.pop_back();
}
inline void dfs(int x)
{
    viz[x]=1;
    for(vector<int>::iterator it=v[x].begin();it!=v[x].end();++it)
    if(!viz[*it])
    {
        t[*it]=x;
        niv[*it]=mini[*it]=niv[x]+1;
        vec.push_back(make_pair(x,*it));
        dfs(*it);
        mini[x]=min(mini[x],mini[*it]);
        if(mini[*it]>=niv[x])
        adauga(x,*it);
    }
    else
    if(t[x]!=*it)
    mini[x]=min(mini[x],niv[*it]);
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;++i)
    {
        f>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(i=1;i<=n;++i)
    if(!viz[i])
    {
        dfs(i);
    }
    g<<nr<<'\n';
    for(i=1;i<=nr;++i)
    {
        sort(sol[i].begin(),sol[i].end());
        for(j=1;j<sol[i].size();++j)
        if(sol[i][j]!=sol[i][j-1])
        g<<sol[i][j-1]<<' ';
        g<<sol[i][sol[i].size()-1]<<'\n';
    }
    return 0;
}