Cod sursa(job #1100074)

Utilizator StexanIarca Stefan Stexan Data 6 februarie 2014 16:25:46
Problema Componente biconexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

ifstream f("biconex.in");
ofstream g("biconex.out");

#define NMAX 100010

const int oo = 200010;

int N,M,Low[NMAX],Level[NMAX],Used[NMAX],Crt,LastCriticalPoint;
vector<int> G[NMAX];
stack<int>Solution;
vector<int>SolutionsVector[NMAX];

void Read(){
    f>>N>>M;
    int x,y;
    for (int i = 1; i <= M; i++) {
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}
void RemoveFromCache(int Node ,int  Neighbour)
{
    while(!Solution.empty() && Solution.top() != Neighbour)
    {
        SolutionsVector[Crt].push_back(Solution.top());
        Solution.pop();
    }
    if (Neighbour) {
        SolutionsVector[Crt].push_back(Neighbour);
    }
    SolutionsVector[Crt++].push_back(Node);
    if( !Solution.empty() )
        Solution.pop();
}

void DFS(int Node,int Father){
    Used[Node] = 1;
    
    Level[Node] = Level[Father] + 1;
    Low[Node] = Level[Node];
    
    int Nr = 0;
    for (vector<int>::iterator it = G[Node].begin(); it != G[Node].end(); ++it) {
        if (Used[*it]==0) {
            Nr++;
            Solution.push(*it);
            DFS(*it,Node);
            Low[Node] = min(Low[Node],Low[*it]);
            if (Low[*it] >= Level[Node]) {
                if (Used[Node] != 2) {
                    Used[Node] = 2;
                    RemoveFromCache(Node, *it);
                    LastCriticalPoint = Node;
                }
            }
        }else{
            Low[Node] = min(Low[Node],Level[*it]);
        }
    }
    if (Father == 0 && Nr > 1) {
        Used[Node] = 2;
        RemoveFromCache(Node, 0);
    }
}

void Solve(){
    for (int i = 1; i <= N; i++) {
        if (Used[i]==0) {
            DFS(i,0);
        }
    }
}

void Write(){
    g<<Crt<<"\n";
    for (int i = 0; i < Crt; i++) {
        for (vector<int>::iterator it = SolutionsVector[i].begin(); it != SolutionsVector[i].end() ; it++) {
            g<<*it<<" ";
        }g<<"\n";
    }
}

int main()
{
    Read();
    Solve();
    Write();
    return 0;
}