Cod sursa(job #874403)

Utilizator TeOOOVoina Teodora TeOOO Data 8 februarie 2013 12:11:33
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
#include <stdio.h>
#include <vector>
#include <stack>
#include <set>
#include <utility>
#include <algorithm>
using namespace std;

//Constante
const int sz = (int)1e5+1;

//Functii
void dfs(int node, int father, int level);
void biconex(pair<int, int> stop);
//Variabile
FILE *in,*out;

int nodes, edges;
int minLevel[sz],depth[sz];

vector <int> graph[sz];
stack <pair<int, int> > st;
vector<set<int> > answer;

int main()
{
    in=fopen("biconex.in","rt");
    out=fopen("biconex.out","wt");

    fscanf(in,"%d%d",&nodes, &edges);
    for(int i=1; i<=edges; ++i)
    {
        int rFrom, rTo;
        fscanf(in,"%d%d",&rFrom,&rTo);
        graph[rFrom].push_back(rTo);
        graph[rTo].push_back(rFrom);
    }

    dfs(1, -1, 1);

    fprintf(out,"%d\n",answer.size());
    vector<set<int> >::iterator it, end = answer.end();
    for(it=answer.begin(); it!=end; ++it)
    {
        set<int>::iterator sit, send = it->end();
        for(sit=it->begin(); sit!=send; ++sit)
            fprintf(out,"%d ",*sit);
        fprintf(out,"\n");
    }

    fclose(in);
    fclose(out);
    return 0;
}

void dfs(int node, int father, int level)
{
    depth[node] = minLevel[node] = level;

    vector <int>::iterator it, end = graph[node].end();

    for(it=graph[node].begin(); it!=end; ++it)
    {
        if(*it == father)
            continue;

        if(depth[*it])
        {
            minLevel[node] = min(minLevel[node], minLevel[*it]);
            continue;
        }
        st.push(make_pair(node, *it));
        dfs(*it, node, level+1);

        minLevel[node] = min(minLevel[node], minLevel[*it]);

        if(level <= minLevel[*it])
            biconex(make_pair(node, *it));
    }
}

void biconex(pair<int, int> stop)
{
    set<int> temp;
    pair<int, int> current;
    do
    {
        current = st.top();
        st.pop();
        temp.insert(current.first);
        temp.insert(current.second);
    } while(current != stop);

    answer.push_back(temp);
    temp.clear();
}