Cod sursa(job #1686301)

Utilizator SilviuIIon Silviu SilviuI Data 12 aprilie 2016 10:30:51
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <stdio.h>
#include <set>
#include <stack>
#include <cstring>
#include <vector>
#define nmax 100010

using namespace std;

int n,m,x,y,nr;
int livmin[nmax],tata[nmax],niv[nmax];
bool fr[nmax],b[nmax];
vector <int> g[nmax];
vector <set <int> > sol;
stack < pair<int,int> > st;
set <int> :: iterator it;

void desc_comp(int i,int j)
{
    nr++; set <int> a;
    while (1) {
        int x=st.top().first,y=st.top().second; st.pop();

        a.insert(x); a.insert(y);

        if (x==i && y==j) break;
    }
    sol.push_back(a);
}

void dfs(int nod)
{
    livmin[nod]=niv[nod]; fr[nod]=true;

    for (int i=0;i<(int)g[nod].size();i++)
        if (!fr[g[nod][i]]) {
            st.push(make_pair(nod,g[nod][i]));
            niv[g[nod][i]]=niv[nod]+1;
            tata[g[nod][i]]=nod;
            dfs(g[nod][i]);
            livmin[nod]=min(livmin[nod],livmin[g[nod][i]]);
            if (livmin[g[nod][i]]>=niv[nod]) desc_comp(nod,g[nod][i]);
    } else
    if (g[nod][i]!=tata[nod]) livmin[nod]=min(livmin[nod],niv[g[nod][i]]);

}

int main()
{
    freopen("biconex.in","r",stdin);
    freopen("biconex.out","w",stdout);

    scanf("%d %d",&n,&m);

    for (int i=1;i<=m;i++) {
        scanf("%d %d",&x,&y);
        g[x].push_back(y); g[y].push_back(x);
    }

    dfs(1);

    printf("%d\n",sol.size());

    for (int i=0;i<sol.size();i++,printf("\n"))
        for (it=sol[i].begin();it!=sol[i].end();it++) printf("%d ",*it);


    return 0;
}