Pagini recente » Cod sursa (job #469022) | Cod sursa (job #550356) | Cod sursa (job #2532807) | Cod sursa (job #1400290) | Cod sursa (job #1890284)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#define f first
#define s second
int n, m, x, y, i, j, a, b, nrComp;
int idx[100005], mini[100005];
vector<int> graph[100005];
vector<int> sol[100005];
stack<pair<int,int> > crtSol;
void DFS(int nod, int par) {
idx[nod] = idx[par] + 1;
mini[nod] = idx[nod];
for(int i = 0 ; i < graph[nod].size() ; i++) {
if(graph[nod][i] != par) {
if(!idx[graph[nod][i]]) {
crtSol.push(make_pair(nod, graph[nod][i]));
DFS(graph[nod][i], nod);
if(mini[graph[nod][i]] >= idx[nod]) {
nrComp++;
do {
a = crtSol.top().f;
b = crtSol.top().s;
sol[nrComp].push_back(b);
crtSol.pop();
} while (a != nod && b != graph[nod][i]);
sol[nrComp].push_back(a);
}
}
mini[nod] = min(mini[nod], mini[graph[nod][i]]);
}
}
/*
if (mini[nod] == idx[nod]) {
nrComp++;
while(crtSol.top() != nod) {
sol[nrComp].push_back(crtSol.top());
crtSol.pop();
}
sol[nrComp].push_back(nod);
}*/
}
int main()
{
fin>>n>>m;
for (i = 1 ; i <= m ; i++) {
fin>>x>>y;
graph[x].push_back(y);
graph[y].push_back(x);
}
DFS(1, 0);
fout<<nrComp<<'\n';
for(i = 1 ; i <= nrComp ; i++) {
for (j = 0 ; j < sol[i].size() ; j++)
fout<<sol[i][j]<<' ';
fout<<'\n';
}
return 0;
}