Pagini recente » Cod sursa (job #785521) | Cod sursa (job #2715934) | Cod sursa (job #2743083) | Cod sursa (job #1411768) | Cod sursa (job #2128966)
#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
#define DIM 100002
#define f first
#define s second
using namespace std;
ifstream in ("biconex.in");
ofstream out("biconex.out");
int n, m, x, y, art[DIM], viz[DIM], nivmin[DIM], lvl[DIM], p;
vector <int> graf[DIM], pctCrit;
vector <vector<int> > cc;
deque <pair<int, int> > q;
void make_cc(int x, int y){
vector <int> v;
while(q.back().f != x || q.back().s != y){
v.push_back(q.back().f);
v.push_back(q.back().s);
q.pop_back();
}
v.push_back(x);
v.push_back(y);
q.pop_back();
cc.push_back(v);
}
void dfs(int nod, int tata, int niv){
viz[nod] = 1;
nivmin[nod] = niv;
lvl[nod] = niv;
for(int i = 0; i < graf[nod].size(); ++ i){
int nodc = graf[nod][i];
if(nodc == tata)
continue;
if(!viz[nodc]){
q.push_back(make_pair(nod, nodc));
dfs(nodc, nod, niv + 1);
nivmin[nod] = min(nivmin[nodc], nivmin[nod]);
if(nivmin[nodc] >= lvl[nod]){
make_cc(nod, nodc);
}
}
else
nivmin[nod] = min(nivmin[nod], lvl[nodc]);
}
if(nod == 1 && graf[1].size() > 1)
pctCrit.push_back(1);
if(nod != 1)
for(int i = 0; i < graf[nod].size(); ++ i){
if(nivmin[graf[nod][i]] >= lvl[nod]){
pctCrit.push_back(nod);
break;
}
}
}
int main() {
p = 1;
in>>n>>m;
for(int i = 1; i <= m; ++ i){
in>>x>>y;
graf[x].push_back(y);
graf[y].push_back(x);
}
dfs(1, 0, 0);
if(p == 1){
out<<cc.size()<<'\n';
for(int i = 0; i < cc.size(); ++ i){
sort(cc[i].begin(), cc[i].end());
cc[i].erase(unique(cc[i].begin(), cc[i].end()), cc[i].end());
// out<<cc[i].size()<<" ";
for(int j = 0; j < cc[i].size(); ++ j){
out<<cc[i][j]<<" ";
}
out<<'\n';
}
}
if(p == 2){
out<<pctCrit.size()<<'\n';
for(vector<int> :: iterator it = pctCrit.begin(); it != pctCrit.end(); ++ it)
out<<*it<<' ';
}
return 0;
}