Pagini recente » Cod sursa (job #2832852) | Cod sursa (job #2113309) | Cod sursa (job #495955) | Cod sursa (job #1586320) | Cod sursa (job #1500813)
#include <bits/stdc++.h>
using namespace std;
vector<int> L[200005];
int viz[200005];
int d[200005];
int low[200005];
bool ap[200005];
deque< pair<int, int> > q;
vector< vector<int> > ret;
void dfs(int in, int depth) {
d[in] = depth;
low[in] = depth;
int children = 0;
for(int i = 0; i < L[in].size(); i ++) {
int j = L[in][i];
if(!viz[j]) {
children ++;
viz[j] = in;
q.push_back(make_pair(j, in));
dfs(j, depth + 1);
low[in] = min(low[in], low[j]);
if(viz[in] == -1 && children > 1) {
ap[in] = true;
vector<int> aux;
aux.clear();
bool ok = true;
while(!q.empty() && ok) {
pair<int, int> punct = q.back();
aux.push_back(punct.first);
aux.push_back(punct.second);
q.pop_back();
if(punct.first == in || punct.second == in)
ok = false;
}
if(aux.size())
ret.push_back(aux);
}
if(viz[in] != -1 && low[j] >= d[in]) {
ap[in] = true;
vector<int> aux;
aux.clear();
bool ok = true;
while(!q.empty() && ok) {
pair<int, int> punct = q.back();
aux.push_back(punct.first);
aux.push_back(punct.second);
q.pop_back();
if(punct.first == in || punct.second == in)
ok = false;
}
if(aux.size())
ret.push_back(aux);
}
}
else if(j != viz[in]) {
if(low[in] > d[j]) {
low[in] = d[j];
}
}
}
}
int main()
{
ifstream f("biconex.in");
ofstream g("biconex.out");
int n, m, x, y;
f >> n >> m;
for(int i = 1; i <= m; i ++) {
f >> x >> y;
L[x].push_back(y);
L[y].push_back(x);
}
for(int i = 1; i <= n; i ++) {
viz[i] = -1;
dfs(i, 1);
vector<int> aux;
aux.clear();
while(!q.empty()) {
pair<int, int> punct = q.back();
aux.push_back(punct.first);
aux.push_back(punct.second);
q.pop_back();
}
if(aux.size())
ret.push_back(aux);
}
/*
for(int i = 1; i <= n; i ++) {
if(ap[i])
g << i << "\n";
}
*/
g << ret.size() << "\n";
for(int i = 0; i < ret.size(); i ++) {
sort(ret[i].begin(), ret[i].end());
if(ret[i].size())
g << ret[i][0] << " ";
for(int j = 1; j < ret[i].size(); j ++) {
if(ret[i][j] != ret[i][j - 1])
g << ret[i][j] << " ";
}
g << "\n";
}
return 0;
}