Cod sursa(job #1276619)

Utilizator lehman97Dimulescu David lehman97 Data 26 noiembrie 2014 17:19:13
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

FILE *f=fopen("biconex.in","r");
FILE *g=fopen("biconex.out","w");


struct vec
 { int x,y;} st[200005];

int n,m,x,y,viz[100005],l[100005],nv[100005],t[100005],rad,nr,i,nrc,k,p,j,sol[100005];
vector <int> v[100005],c[200005];




void df(int nod)
{
    int i,x,y;
    viz[nod]=1;
    l[nod]=nv[nod];
    x=nod;
    for(i=0;i<v[nod].size();i++)
        if(!viz[v[nod][i]])
        {
            y=v[nod][i];
            k++; st[k].x=x; st[k].y=y;
            nv[v[nod][i]]=nv[nod]+1;
            t[v[nod][i]]=nod;
            if(nod==rad)nr++;
            df(v[nod][i]);
            if(l[nod]>l[v[nod][i]]) l[nod]=l[v[nod][i]];
            if(l[v[nod][i]] >= nv[nod])
            {
                nrc++;
            while(!(st[k].x==x && st[k].y==y))
            {
                c[nrc].push_back(st[k].x);
                c[nrc].push_back(st[k].y);
                k--;
             }
          c[nrc].push_back(st[k].x);
          c[nrc].push_back(st[k].y);
           k--;

         }
        }
        else
        if(v[nod][i]!=t[nod] && l[nod]>nv[v[nod][i]])l[nod]=nv[v[nod][i]];
}


void citire()
{
    int i;
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
}

int main()
{
    citire();
    for(i=1;i<=n;i++)
    if(!viz[i])
    {
        nv[i]=1;
        rad=i;
        nr=0;
        df(i);
    }
   fprintf(g,"%d\n",nrc);
   for(i=1;i<=nrc;i++)
   {
      sort(c[i].begin(),c[i].end());
      p=0;
      for(j=0;j<c[i].size();j++)
        if (!j || c[i][j]!=c[i][j-1])
        {
            p++;
            sol[p]=c[i][j];
        }
    for(j=1;j<=p;j++)
    fprintf(g,"%d ",sol[j]);
    fprintf(g,"\n");
    }
    fclose(g);
    return 0;
}