Pagini recente » Cod sursa (job #497670) | Cod sursa (job #542600) | Cod sursa (job #289549) | Cod sursa (job #3258738) | Cod sursa (job #1858488)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> G[1000005];
vector< pair<int, int> > M;
int viz[100005];
vector<int> v;
vector< vector<int> > ans;
int fi, se;
void df(int x, int prec) {
viz[x] = 2;
for(int j = 0; j < G[x].size(); j ++) {
if(G[x][j] != prec) {
int lucky = viz[ G[x][j] ];
if(!lucky) {
df(G[x][j], x);
viz[x] = min(viz[x], viz[ G[x][j] ]);
}
else if(lucky == 1) viz[x] = 1;
}
}
}
int main()
{
ifstream f("biconex.in");
ofstream g("biconex.out");
int n, m;
f >> n >> m;
int x, y;
for(int i = 1; i <= m; i ++) {
f >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
M.push_back( {x, y} );
}
for(int i = 0; i < m; i ++) {
viz[ M[i].first ] = 1;
viz[ M[i].second ] = 1;
fi = M[i].first;
se = M[i].second;
df(se, fi);
viz[ M[i].first ] = 1;
viz[ M[i].second ] = 1;
df(fi, se);
viz[ M[i].first ] = 1;
viz[ M[i].second ] = 1;
bool exista = false;
int kkt = 0;
for(int j = 1; j <= n; j ++)
if(viz[j] == 1) {
kkt ++;
}
if(kkt == 2)
exista = true;
if(exista) {
v.push_back(fi);
v.push_back(se);
for(int j = 1; j <= n; j ++)
viz[j] = 0;
}
else {
for(int j = 1; j <= n; j ++) {
if(viz[j] == 1) v.push_back(j);
viz[j] = 0;
}
}
ans.push_back(v);
v.clear();
}
sort(ans.begin(), ans.end());
for(int i = 1; i < ans.size(); i ++) {
if(ans[i] == ans[i - 1]) {
for(int j = i; j < ans.size() - 1; j ++)
ans[j] = ans[j + 1];
ans.pop_back();
i --;
}
}
g << ans.size() << "\n";
for(int i = 0; i < ans.size(); i ++) {
for(int j = 0; j < ans[i].size(); j ++)
g << ans[i][j] << " ";
g << "\n";
}
return 0;
}