Cod sursa(job #1089866)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 21 ianuarie 2014 23:43:47
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.93 kb
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector <int> G[100005];
vector <int> Solution[200005];
int Result,N,M;
bool Use[100005],Critical[100005];
int Level[100005],MinLevel[100005];
stack <int> S1;
stack <int> S2;
void Read()
{
    int i;
    f>>N>>M;
    for(i=1;i<=M;i++)
    {
        int x,y;
        f>>x>>y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
    for(i=1;i<=N;i++)
        MinLevel[i]=1000001,Level[i]=-1;
}
void Sol(int X,int Y)
{
    int i;
    int node1=0,node2=0;
    ++Result;
    while(node1!=X && node2!=Y)
    {

        node1=S1.top();
        node2=S2.top();
        Solution[Result].push_back(node1);
        Solution[Result].push_back(node2);
        S1.pop();
        S2.pop();
    }
}
void DFS(int father,int node)
{
    Use[node]=1;
    Level[node]=MinLevel[node]=Level[father]+1;
    for(unsigned int i=0;i<G[node].size();i++)
    {
        int neighbour=G[node][i];
        if(neighbour==father)
            continue;
        if(Use[neighbour]==0)
        {
            S1.push(node);
            S2.push(neighbour);
            DFS(node,neighbour);
            MinLevel[node]=min(MinLevel[node],MinLevel[neighbour]);
            if(Level[node]<=MinLevel[neighbour])
                Sol(node,neighbour);
        }

        else
             MinLevel[node]=min(MinLevel[node],Level[neighbour]);
    }

}
void Print()
{
    int i;
    g<<Result<<"\n";
    for(i=1;i<=Result;i++)
    {
        unsigned int j=0;
        sort(Solution[i].begin(), Solution[i].end());
        Solution[i].erase(unique(Solution[i].begin(), Solution[i].end()), Solution[i].end());
        for(j=0;j<Solution[i].size();j++)
            g<<Solution[i][j]<<" ";
        g<<"\n";
    }
}
int main()
{
    Read();
    DFS(0,1);
    Print();
    return 0;
}