Pagini recente » Cod sursa (job #3165915) | Cod sursa (job #3138194) | Cod sursa (job #1774478) | Cod sursa (job #1950641) | Cod sursa (job #2668220)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define MAX 100001
using namespace std;
ifstream in ("biconex.in");
ofstream out ("biconex.out");
int N, M;
bool viz[MAX];
int tata[MAX];
queue<pair<int,int>> q;
queue<pair<int,int>> bck;
vector<int> graf[MAX];
vector<vector<int>> conex;
void dfs ( int x ){
viz[x] = true;
for( auto y : graf[x])
if( !viz[y]){
q.push(make_pair(x,y));
tata[y] = x;
dfs(y);
}
else if (y != tata[x]){
bck.push(make_pair(x,y));
}
}
int main(){
in >> N >> M;
for( int i = 0; i < M ; i++){
int x, y;
in >> x >> y;
graf[x].push_back(y);
graf[y].push_back(x);
}
dfs(1);
while( !q.empty() ){
vector<int> comp;
if( !bck.empty() && bck.front().second == q.front().first){
while( q.front().second != bck.front().first && !q.empty()){
comp.push_back(q.front().first);
//out << "(" << q.front().first << "; " << q.front().second << ") ";
q.pop();
}
//out << "(" << q.front().first << "; " << q.front().second << ") ";
bck.pop();
bck.pop();
//out << bck.front().first << "," << bck.front().second;
}
//out << "(" << q.front().first << "; " << q.front().second << ") ";
comp.push_back(q.front().first);
comp.push_back(q.front().second);
q.pop();
conex.push_back(comp);
}
out << conex.size() << "\n";
for( auto v : conex){
for ( auto x : v)
out << x << " ";
out << "\n";
}
return 0;
}