Cod sursa(job #526080)

Utilizator giuliastefGiulia Stef giuliastef Data 27 ianuarie 2011 12:41:28
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
// Componente biconexe

#include <fstream>
#include <vector>
#include <stack> 
#define MAXN 100010
using namespace std;
int n,m,vizitat[MAXN],nivel[MAXN];
vector <int> graf[MAXN];
stack <pair<int,int> > stiva;
vector <vector <int> > C;
void read()
{
     int i,x,y;
     ifstream f("biconex.in");
     f>>n>>m;
     for(i=1;i<=m;i++)
     {
      f>>x>>y;
      graf[x].push_back(y);
      graf[y].push_back(x);
     }
     f.close();
}
void scrie_componenta(int x, int y)
{
     vector <int> comp;
     int i,j;
     do {
        i = stiva.top().first, j = stiva.top().second;
        stiva.pop();
        comp.push_back(i), comp.push_back(j);
    }
    while (i != x || j != y);
    C.push_back(comp);
}
void puncte_critice(int nod, int parinte, int niv)
{
     int i,x;
     vizitat[nod]=niv, nivel[nod]=niv;
     for(i=0;i<graf[nod].size();i++)
     {
      x=graf[nod][i];
      if(!vizitat[x])
      {
       stiva.push(make_pair(x,nod));
       puncte_critice(x,nod,niv+1);
       if(nivel[x]<nivel[nod])
        nivel[nod]=nivel[x];
       if(nivel[x]>=vizitat[nod])
         scrie_componenta(x,nod);
      }
     else
      if(x!=parinte&&vizitat[x]<nivel[nod]) nivel[nod]=vizitat[x];
   }
}
void solve()
{
    int i;
    for(i=1;i<=n;i++)
     if(!vizitat[i])
      puncte_critice(i,0,0); 
}
void write()
{
    int i,j;
    ofstream g("biconex.out");
    g<<C.size()<<"\n";
    for(i=0;i<C.size();i++)
    {
      sort(C[i].begin(), C[i].end());
      C[i].erase(unique(C[i].begin(), C[i].end()), C[i].end());
      for(j=0;j<C[i].size();j++)
       g<<C[i][j]<<" ";
      g<<"\n";
    }
    g.close();
}
int main()
{
    read();
    solve();
    write();
    return 0;
}