Pagini recente » Borderou de evaluare (job #2548199) | Cod sursa (job #590656) | Cod sursa (job #1890321)
#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]) {
a = 0;
b = 0;
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]]);
}
}
}
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;
}