Pagini recente » Cod sursa (job #1813148) | Cod sursa (job #483273) | Cod sursa (job #216242) | Cod sursa (job #580996) | Cod sursa (job #1027243)
#include <iostream>
#include <fstream>
#include <vector>
#define N_MAX 100001
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector <int> v[N_MAX];
bool visited[N_MAX];
int cc = 0, N, M, pre[N_MAX], comp[20000][2000], end[N_MAX], art[N_MAX], na;
void DFS(int node)
{
bool check = 1;
for(int i = 0; i < v[node].size(); i++)
{
//cout<<i<<endl;
if(visited[v[node][i]] && v[node][i] != pre[node] && !end[v[node][i]])
{
art[na++] = v[node][i];
//pre[v[node][i]] = node;
}
if(!visited[v[node][i]])
{
check = 0;
visited[v[node][i]] = true;
pre[v[node][i]] = node;
DFS(v[node][i]);
}
}
if(check == 1) end[node] = 1;
}
void DFSc(int node)
{
for(int i = 0; i < v[node].size(); i++)
{
//cout<<"NODE"<<node<<" "<<v[node][i];
if(!visited[v[node][i]] /*&& v[node][i] != art[na]*/)
{
visited[v[node][i]] = true;
out << v[node][i] << " ";
if(v[node][i] != art[na]) DFSc(v[node][i]);
}
if(v[node][i] == art[na] && pre[node] != v[node][i])
{
//cout<<"OF"<<art[na];
na++;
out <<"\n"<<art[na-1]<<" ";
DFSc(art[na-1]);
}
}
}
int main()
{
in >> N >> M;
for(int i = 0; i < M; i++)
{
int x, y;
in >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
visited[1] = true;
DFS(1);
for(int i = 1; i <= N; i++)
{
visited[i] = 0;
}
out << na + 1 << "\n";
na = 0;
visited[art[na]] = 1;
out << art[na] << " ";
DFSc(art[na]);
return 0;
}