Pagini recente » Cod sursa (job #3178308) | Cod sursa (job #1422691) | Cod sursa (job #997294) | Cod sursa (job #2165833) | Cod sursa (job #2199795)
#include <bits/stdc++.h>
#define NMAX 100005
#define MMAX 200005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, counter;
int visited[NMAX], stage[NMAX], lowStage[NMAX], father[NMAX];
vector <int> edges[MMAX], component[MMAX];
stack < pair <int, int> > edge;
pair <int, int> aux;
void CreateComponent(int node, int neighbor) {
++counter;
do {
aux=edge.top();
component[counter].push_back(aux.first);
component[counter].push_back(aux.second);
edge.pop();
}
while((aux.first!=node || aux.second!=neighbor) && (aux.second!=node || aux.first!=neighbor));
}
void DFS(int node) {
visited[node]=1;
lowStage[node]=stage[node];
for(unsigned i=0; i<edges[node].size(); ++i) {
int neighbor = edges[node][i];
if(stage[neighbor]<stage[node] && neighbor!=father[node]) {
edge.push(make_pair(node,neighbor));
if(!visited[neighbor]) {
stage[neighbor]=stage[node]+1;
father[neighbor]=node;
DFS(neighbor);
lowStage[node]=min(lowStage[node],lowStage[neighbor]);
if(lowStage[neighbor]>=stage[node]) CreateComponent(node,neighbor);
}
else lowStage[node]=min(lowStage[node],stage[neighbor]);
}
}
}
int main() {
int x,y;
fin>>n>>m;
for(int i=1; i<=m; ++i) {
fin>>x>>y;
edges[x].push_back(y);
edges[y].push_back(x);
}
visited[1]=1; stage[1]=1; DFS(1);
fout<<counter<<endl;
for(int i=1; i<=counter; ++i) {
sort(component[i].begin(), component[i].end());
fout<<component[i][0]<<' ';
for(unsigned j=1; j<component[i].size(); ++j)
if(component[i][j]!=component[i][j-1]) fout<<component[i][j]<<' ';
fout<<endl;
}
return 0;
}