Cod sursa(job #1478024)

Utilizator SilviuIIon Silviu SilviuI Data 27 august 2015 16:21:19
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <stdio.h>
#include <vector>
#include <bitset>
#include <set>
#define nmax 100010
using namespace std;
struct date { int x,y; };
int n,i,j,m,x,y,b,livmin[nmax],niv[nmax],tata[nmax];
vector <int> g[nmax];
bitset <nmax> fr;
vector < set<int> > sol;
set <int>::iterator it;
date stiva[nmax];
void desc_into_comp(int x,int y)
{
    set <int> a;
    do {
        a.insert(stiva[b].x); a.insert(stiva[b].y); b--;
    } while (stiva[b+1].x!=x || stiva[b+1].y!=y);
    sol.push_back(a);
}
void dfs(int nod)
{
    fr[nod]=1; livmin[nod]=niv[nod];
    for (unsigned int i=0;i<g[nod].size();i++)
        if (fr[g[nod][i]]==0) {
            niv[g[nod][i]]=niv[nod]+1; tata[g[nod][i]]=nod;
            b++; stiva[b].x=nod; stiva[b].y=g[nod][i];
            dfs(g[nod][i]);
            if (livmin[nod]>livmin[g[nod][i]]) livmin[nod]=livmin[g[nod][i]];
            if (livmin[g[nod][i]]>=niv[nod]) desc_into_comp(nod,g[nod][i]);
    } else
    if (g[nod][i]!=tata[nod] && livmin[nod]>niv[g[nod][i]]) livmin[nod]=niv[g[nod][i]];
}
int main() {
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
scanf("%d %d",&n,&m);
for (i=1;i<=m;i++) {
    scanf("%d %d",&x,&y);
    g[x].push_back(y); g[y].push_back(x);
}
for (i=1;i<=n;i++)
   if (fr[i]==0) { niv[i]=1; dfs(i); }
printf("%d\n",sol.size());
for (i=0;i<sol.size();i++) {
    for (it=sol[i].begin();it!=sol[i].end();it++) printf("%d ",*it);
    printf("\n");
}
return 0;
}