Cod sursa(job #1474920)

Utilizator SilviuIIon Silviu SilviuI Data 23 august 2015 09:49:24
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <bitset>
#include <stack>
#include <set>
#define nmax 100010
using namespace std;
struct date { int x,y; };
int x,y,n,m,i,j,nr,k,livmin[nmax],niv[nmax],tata[nmax],b;
bitset <nmax> fr;
vector <int> g[nmax];
vector <vector<pair<int,int> > > sol;
date stiva[nmax];
void desc_into_comp(int x,int y)
{
    vector <pair<int,int> > a; a.clear();
    do {
        a.push_back(make_pair(stiva[b].x,stiva[b].y)); b--;
    } while (stiva[b+1].x!=x || stiva[b+1].y!=y);
    sol.push_back(a);
}
void dfs(int x)
{
    unsigned int i; livmin[x]=niv[x]; fr[x]=1;
    for (i=0;i<g[x].size();i++) {
       if (fr[g[x][i]]==0) {
           niv[g[x][i]]=niv[x]+1; tata[g[x][i]]=x;
           b++; stiva[b].x=x; stiva[b].y=g[x][i];
           if (x==i) nr++;
           dfs(g[x][i]);
           if (livmin[x]>livmin[g[x][i]]) livmin[x]=livmin[g[x][i]];
           if (livmin[g[x][i]]>=niv[x]) desc_into_comp(x,g[x][i]);
    } else
    if (g[x][i]!=tata[x] && livmin[x]>niv[g[x][i]]) livmin[x]=niv[g[x][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) { k++; nr=0; niv[i]=1; dfs(i); }
printf("%d\n",sol.size());
for (i=0;i<sol.size();i++) {
    set <int> a; a.clear(); set <int>::iterator it;
    for (j=0;j<sol[i].size();j++) a.insert(sol[i][j].first),a.insert(sol[i][j].second);
    for (it=a.begin();it!=a.end();it++) printf("%d ",*it);
    printf("\n");
}
return 0;
}