Pagini recente » Cod sursa (job #544203) | Cod sursa (job #1535073) | Cod sursa (job #2917031) | Cod sursa (job #2310712) | Cod sursa (job #1691299)
#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;
}