Pagini recente » Cod sursa (job #2149341) | Cod sursa (job #1881175) | Cod sursa (job #37558) | Cod sursa (job #529745) | Cod sursa (job #3040035)
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const ll NMAX = 1000001;
const ll INF = (1LL << 60);
const ll nrbits = 17;
const ll MOD = 9973;
vector <vector <int> > comp;
int low[NMAX];
int lvl[NMAX];
vector <int> v[NMAX];
vector <int> stiva;
vector <int> noduri;
int pa[NMAX];
void DFS(int node){
noduri.push_back(node);
low[node] = 2e9;
for(auto x : v[node]){
if(lvl[x] == 0){
lvl[x] = lvl[node] + 1;
pa[x] = node;
DFS(x);
low[node] = min(low[node], low[x]);
}else if(lvl[x] + 1 != lvl[node]){ /// doar lvl[x] < lvl[node]
low[node] = min(low[node], lvl[x]);
}
}
if(lvl[node] > 1 && low[node] >= lvl[node] - 1){
vector <int> nou;
nou.push_back(pa[node]);
while(noduri.back() != node){
nou.push_back(noduri.back());
noduri.pop_back();
}
nou.push_back(node);
noduri.pop_back();
comp.push_back(nou);
}
}
int main() {
//#ifdef HOME
ifstream cin("biconex.in");
ofstream cout("biconex.out");
//#endif // HOME
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, i;
cin >> n >> m;
for(i = 1; i <= m; i++){
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
for(i = 1; i <= n; i++){
if(!lvl[i]){
lvl[i] = 1;
DFS(i);
if(noduri.size() > 1){
comp.push_back(noduri);
}
noduri.clear();
}
}
cout << comp.size() << "\n";
for(auto x : comp){
for(auto y : x){
cout << y << " ";
}
cout << "\n";
}
return 0;
}