Cod sursa(job #1241030)

Utilizator RaduGabriel2012Dinu Radu RaduGabriel2012 Data 12 octombrie 2014 15:00:27
Problema Componente biconexe Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");

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

 int n,m,k,use[100005],niv[100005],mn[100005],inf=2147000000,nrc,sol[100005];

 vector <int> v[100005],c[200005];

 void DFS(int x)
 { int i,y;
       use[x]=1;mn[x]=niv[x];

    for(i=0;i<v[x].size();i++)
    { y=v[x][i];

       if (use[y]) continue;

       use[y]=1;

        k++; st[k].x=x; st[k].y=y;

        niv[y]=niv[x]+1;

        DFS(y);

      mn[x]=min(mn[x],mn[y]);

        if (mn[x]>=niv[x])
         { 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--;

         }

    }

   for(i=0;i<v[x].size();i++)
   { y=v[x][i];
    if (niv[y]<niv[x]-1) mn[x]=min(mn[x],niv[y]);
   }
 }

int main()
{ int i,j,x,y,p;
    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 (!use[i]) DFS(i);

  g<<nrc<<"\n";

 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++)
     g<<sol[j]<<" ";

   g<<"\n";
  }
    return 0;
}