Cod sursa(job #302959)

Utilizator alecmanAchim Ioan Alexandru alecman Data 9 aprilie 2009 13:57:46
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.02 kb
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>

using namespace std;

#define INPUT "biconex.in"
#define OUTPUT "biconex.out"
#define pb push_back
#define mp make_pair

const long NMAX = 100001;

FILE *fin = fopen(INPUT, "r"), *fout = fopen(OUTPUT, "w");

long N, M;
long niv[ NMAX ], low[ NMAX ];
vector<long> List[ NMAX ];
vector< vector<long> > Final;
stack<pair<long, long > > stk;

inline long Min(long _X, long _Y)
{
  if(_X < _Y) return _X;
  return _Y;
}

void readData()
{
  long Node1, Node2;
  
  fscanf(fin, "%ld %ld", &N, &M);
  
  for(long i = 1; i <= M; ++i)
  {
    fscanf(fin, "%ld %ld", &Node1, &Node2);
    
    List[ Node1 ].pb(Node2);
    List[ Node2 ].pb(Node1);
  }
}

void component(long x, long y)
{
  vector<long> tmp;
  long node1, node2;
  
  do{
    node1 = stk.top().first;
    node2 = stk.top().second;
    stk.pop();
    tmp.pb(node1);
    tmp.pb(node2);
    
  }while(x != node1 || y != node2);
  Final.pb(tmp);
}

void DFS(long node, long father, long level)
{
  vector<long>::iterator it;
  
  niv[ node ] = low[ node ] = level;
  
  for(it = List[ node ].begin(); it != List[ node ].end(); ++it)
  {
    if(*it == father) continue;
    if(niv[ *it ] == -1)
    {
      stk.push(mp(node, *it));
      DFS(*it, node, level+1);
      
      low[ node ] = Min(low[ node ], low[ *it ]);
      
      if(low[ *it ] >= niv[ node ])
        component(node, *it);
    }
    else
      low[ node ] = Min(low[ node ], niv[ *it ]);
  }
}

void display()
{
  vector<long>::iterator it;
  
  fprintf(fout, "%ld\n", Final.size());
  
  for(long i = 0; i < Final.size(); ++i)
  {
    sort(Final[ i ].begin(), Final[ i ].end());
    Final[ i ].erase(unique(Final[ i ].begin(), Final[ i ].end()), Final[ i ].end());
    
    for(it = Final[ i ].begin(); it != Final[ i ].end(); ++it)
      fprintf(fout, "%ld ", *it);
    fprintf(fout, "\n");
  }
}

int main()
{
  readData();
  
  for(long i = 1; i <= N; ++i)
    niv[ i ] = low[ i ] = -1;
    
  DFS(1, 0, 0);
  
  display();
  
  fclose(fin);
  fclose(fout);
  
  return 0;
}