Cod sursa(job #954750)

Utilizator blechereyalBlecher Eyal blechereyal Data 29 mai 2013 23:15:04
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.07 kb

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define NMAX 100003

using namespace std;
int N,M,no_components,no;

int num[NMAX],low[NMAX];
vector <int> *graph;
vector <int> solution[NMAX];
pair <int,int> p;
stack <pair <int,int> > st;
ifstream in("biconex.in");
ofstream out("biconex.out");
int min (int x,int y){
if (x<y) return x;
return y;
}

void dfs(int node, int father)
{
int w,x,y;
no++;
num[node]=no;
low[node]=no;
for (vector<int>::iterator it=graph[node].begin();it!=graph[node].end();it++)
    {
     w=*it;
     if (father==node) continue;
     if (num[w]==0)
        {
        st.push(make_pair(node,w));
        dfs(w,node);
        low[node]=min(low[node],low[w]);
        if (low[w]>=num[node])
        {
            no_components++;
            solution[no_components].push_back(st.top().first);
            do
            {

            x=st.top().first;
            y=st.top().second;
            solution[no_components].push_back(y);
            st.pop();

            }while ((x!=node) && (y!=w));
            solution[no_components].push_back(x);
        }



        }
    else if ((num[w]<num[node])&&(w!=father))
             {
                st.push(make_pair(node,w));
                low[node]=min(low[node],num[w]);
             }

    }

}
int main()
{

    int x,y,i;
    in>>N>>M;
    graph=new vector<int> [N+1];
    for (i=1;i<=M;i++)
    {
        in>>x>>y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    no=0;
    no_components=0;
    for (i=1;i<=N;i++)
    num[i]=0;
    for (i=1;i<=N;i++)
    if (num[i]==0) dfs(i,0);

    out<<no_components<<"\n";

    for(i=1;i<=no_components;i++)
    {
    vector<int>::iterator uni;
    sort(solution[i].begin(),solution[i].end());
    uni=unique(solution[i].begin(),solution[i].end());
    solution[i].resize(distance(solution[i].begin(),uni));
    for (vector<int>::iterator it=solution[i].begin();it!=solution[i].end();it++)
    out<<*it<<" ";
    out<<"\n";
    }
}