Cod sursa(job #457217)

Utilizator vladiiIonescu Vlad vladii Data 18 mai 2010 16:48:57
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
#define maxn 100010
#define inf 99999999

int N, M, Nr;
int low[maxn], lev[maxn];
vector<int> G[maxn], CC[maxn];
stack<pair<int, int> > S;

void CompB(int x, int y) {
    Nr++;
    int i, j;
    i = S.top().first;
    j = S.top().second;
    S.pop();
    CC[Nr].push_back(i); CC[Nr].push_back(j);
    while(i != x || j != y) {
         i = S.top().first;
         j = S.top().second;
         S.pop();
         CC[Nr].push_back(i); CC[Nr].push_back(j);
    }
}

void DFS(int nod, int prev) {
    lev[nod] = lev[prev] + 1;
    low[nod] = inf;
    for(vector<int>::iterator it=G[nod].begin(); it!=G[nod].end(); it++) {
         if((*it) != prev) {
              if(!lev[(*it)]) {
                   S.push(make_pair(nod, *it));
                   DFS(*it, nod);
                   low[nod] = min(low[nod], low[*it]);
                   if(low[*it] >= lev[nod]) {
                        CompB(nod, *it);
                   }
              }
              else {
                   low[nod] = min(low[nod], lev[*it]); //muchie de intoarcere
              }
         }
    }
}   

int main() {
    FILE *f1=fopen("biconex.in", "r"), *f2=fopen("biconex.out", "w");
    int i, j, p;
    fscanf(f1, "%d %d\n", &N, &M);
    for(i=1; i<=M; i++) {
         fscanf(f1, "%d %d\n", &j, &p);
         G[j].push_back(p);
         G[p].push_back(j);
    }
    
    DFS(1, 0);
    
    fprintf(f2, "%d\n", Nr);
    for(i=1; i<=Nr; i++) {
         sort(CC[i].begin(), CC[i].end());
         CC[i].erase(unique(CC[i].begin(), CC[i].end()), CC[i].end());
         for(j=0; j<CC[i].size(); j++) {
              fprintf(f2, "%d ", CC[i][j]);
         }
         fprintf(f2, "\n");
    }
    
    fclose(f1); fclose(f2);
    return 0;
}