Pagini recente » Cod sursa (job #2403343) | Cod sursa (job #2913559) | Cod sursa (job #2333633) | Cod sursa (job #1038367) | Cod sursa (job #2135037)
#include <fstream>
#include <vector>
#define DIM 1000002
using namespace std;
ifstream in ("biconex.in");
ofstream out("biconex.out");
int n, x, y, tip, m, viz[DIM], low[DIM], lvl[DIM], nr1, art_nod[DIM];
vector<int> graf[DIM], q;
vector<vector<int> > cb;
void get_cb(int nod){
vector<int> newCB;
while(q.back() != nod){
newCB.push_back(q.back());
++ art_nod[q.back()];
q.pop_back();
}
newCB.push_back(q.back());
++ art_nod[q.back()];
cb.push_back(newCB);
}
void dfs(int nod, int niv, int tata){
viz[nod] = 1;
low[nod] = 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(nodc);
dfs(nodc, niv + 1, nod);
low[nod] = min(low[nod], low[nodc]);
if(low[nodc] >= lvl[nod])
get_cb(nod);
}
else
low[nod] = min(low[nod], lvl[nodc]);
}
}
void afis_cb(){
out<<cb.size()<<'\n';
for(int i = 0; i < cb.size(); ++ i){
// out<<cb[i].size()<<" ";
for(int j = 0; j < cb[i].size(); ++ j)
out<<cb[i][j]<<" ";
out<<'\n';
}
}
void afis_nodes(){
int nr = 0;
for(int i = 1; i <= n; ++ i)
if(art_nod[i] > 1)
++ nr;
out<<nr<<'\n';
for(int i = 1; i <= n; ++ i)
if(art_nod[i] > 1)
out<<i<<" ";
}
void afis_edges(){
int nr = 0;
for(int i = 0; i < cb.size(); ++ i)
if(cb[i].size() == 2)
++ nr;
out<<nr<<'\n';
for(int i = 0; i < cb.size(); ++ i)
if(cb[i].size() == 2)
out<<cb[i][0]<<" "<<cb[i][1]<<'\n';
}
int main() {
tip = 1;
in>>n>>m;
for(int i = 1; i <= m; ++ i){
in>>x>>y;
graf[x].push_back(y);
graf[y].push_back(x);
}
q.push_back(1);
dfs(1, 0, 0);
switch(tip){
case 1:afis_cb(); break;
case 2:afis_nodes(); break;
case 3:afis_edges(); break;
}
return 0;
}