Cod sursa(job #1691299)

Utilizator Bijoux12Andreea Gae Bijoux12 Data 17 aprilie 2016 20:25:59
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.25 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

vector<vector<int> > graph;
vector<bool> visited;
vector<int> nivel;
vector< vector < pair <int,int> > > sol;
stack< pair <int, int> > stiv;
int n, m,nr;

void subp(int x)
{
    int y,sem=0;
    y=nivel[stiv.top().first];
    while(y!=x && !stiv.empty())
    {
        sol[nr].push_back(make_pair(stiv.top().first,stiv.top().second));
        stiv.pop();
        y=nivel[stiv.top().first];
    }
    sol[nr].push_back(make_pair(stiv.top().first,stiv.top().second));
    stiv.pop();
    nr++;
    while(!stiv.empty())
    {
        sol[nr].push_back(make_pair(stiv.top().first,stiv.top().second));
        stiv.pop();
        sem=1;
    }
    if(sem)
        nr++;
}

void dfs(int vertex)
{
	if(vertex<0 || vertex>n-1)
        return;
    visited[vertex]=true;
	for (int i = 0; i <graph[vertex].size();i++)
		{
		    if (!visited[graph[vertex][i]])
            {
                visited[graph[vertex][i]]=true;
                stiv.push(make_pair(vertex, graph[vertex][i]));
                nivel[graph[vertex][i]]=nivel[vertex]+1;
                dfs(graph[vertex][i]);
            }
            else
                if( nivel[graph[vertex][i]]+1 < nivel[vertex])
                    {
                        stiv.push(make_pair(vertex, graph[vertex][i]));
                        subp(nivel[graph[vertex][i]]);
                    }
		}

}

int main()
{
	int i, j, x, y;
	nr=0;
	f >> n >> m;
	graph.resize(n);
	visited.resize(n,false);
	sol.resize(n);
	nivel.resize(n,0);
	for (i = 0; i < m;i++)
	{
		f >> x >> y;
		x--;
		y--;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	dfs(0);
	while(!stiv.empty())
        {
            sol[nr].push_back(make_pair(stiv.top().first,stiv.top().second));
            stiv.pop();
        }
    nr++;
    g<<nr<<endl;
	for(i=0;i<nr;i++)
        {
            for(int j=0;j<sol[i].size();j++)
                if(sol[i].size()==1)
                    g<<sol[i][j].first+1<<" "<<sol[i][j].second+1<<" ";
                else
                    g<<sol[i][j].first+1<<" ";
            g<<endl;
        }
	return 0;
}