Cod sursa(job #1097545)

Utilizator TeOOOVoina Teodora TeOOO Data 3 februarie 2014 16:15:42
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.04 kb
//Include
#include <stdio.h>
#include <vector>
#include <set>
#include <algorithm>
#include <stack>
using namespace std;

FILE *in, *out;

//Definitii
#define pb push_back
#define edge pair<int, int>
#define mp make_pair

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

//Functii
void dfs(int node, int father, int level);
void biconex(edge stop);

//Variabile
int nodes, edges;
int minLevel[sz];
vector <int> graph[sz];
stack <edge> stacky;
vector < set<int> > answer;

//Main
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 from, to;
        fscanf(in,"%d%d", &from, &to);
        graph[from].pb(to);
        graph[to].pb(from);
    }

    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)
{
    minLevel[node] = level;
    vector<int>::iterator it, end = graph[node].end();
    for(it = graph[node].begin(); it!=end; ++it)
    {
        if(*it == father)
            continue;

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

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



void biconex(edge stop)
{
    set <int> temp;
    edge current;

    do
    {
        current = stacky.top();
        stacky.pop();
        temp.insert(current.first);
        temp.insert(current.second);
    } while(current != stop);

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