Pagini recente » Cod sursa (job #2030746) | Cod sursa (job #430544) | Cod sursa (job #2771143) | Cod sursa (job #3227600) | Cod sursa (job #2145812)
#include <bits/stdc++.h>
#define MAXN 100010
inline int min(int a, int b){return a < b ? a : b;}
int n, m, a, b;
std::vector <std::vector <int>> M;
std::vector <int> G[1 + MAXN], emptyVec;
std::stack <std::pair<int, int>> S;
int depth[1 + MAXN], lowlink[1 + MAXN];
void writeComponent(int node){
bool ok = 1;
M.push_back(emptyVec);
while(ok){
if(S.top().second == node) ok = 0;
M[M.size() - 1].push_back(S.top().first);
S.pop();
}
M[M.size() - 1].push_back(node);
}
void tarjan(int node, int fth){
depth[node] = lowlink[node] = depth[fth] + 1;
for(auto y: G[node]){
if(!depth[y]){
S.push({y, node});
tarjan(y, node);
lowlink[node] = min(lowlink[node], lowlink[y]);
if(lowlink[y] >= depth[node]) writeComponent(node);
}
else lowlink[node] = min(lowlink[node], depth[y]);
}
}
int main(){
FILE*fi,*fo;
fi = fopen("biconex.in","r");
fo = fopen("biconex.out","w");
fscanf(fi,"%d%d", &n, &m);
for(int i = 1; i <= m; i++){
fscanf(fi,"%d%d", &a, &b);
G[a].push_back(b);
G[b].push_back(a);
}
for(int i = 1; i <= n; i++) if(!depth[i]) tarjan(i, 0);
fprintf(fo,"%d\n", M.size());
for(int i = 0; i < M.size(); i++){
for(int j = 0; j < M[i].size(); j++) fprintf(fo,"%d ", M[i][j]);
fprintf(fo,"\n");
}
return 0;
}