Pagini recente » Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #3335901) | Borderou de evaluare (job #3303917) | Cod sursa (job #3328955)
#include <vector>
#include <fstream>
using namespace std;
const int NMAX=100100;
int x,y,n,m,comp,Niv[NMAX],Nma[NMAX],viz[NMAX],vf,S[NMAX];
vector<int>G[NMAX],CB[NMAX];
ifstream f("biconex.in");
ofstream g("biconex.out");
void DFS(int nod,int tata) {
S[++vf]=nod;
Niv[nod]=Niv[tata]+1;
viz[nod]=1;
Nma[nod]=Niv[nod];
for(const int&i:G[nod]) {
if(i==tata) {
continue;
}
if(viz[i]==1) {
Nma[nod]=min(Nma[nod],Niv[i]);
} else {
DFS(i,nod);
Nma[nod]=min(Nma[nod],Nma[i]);
if(Niv[nod]<=Nma[i]) {
comp++;
while(S[vf]!=i) {
CB[comp].push_back(S[vf--]);
}
CB[comp].push_back(i);
vf--;
CB[comp].push_back(nod);
}
}
}
}
int main() {
f>>n>>m;
while(m--) {
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
DFS(1,0);
g<<comp<<'\n';
for(int i=1; i<=comp; ++i) {
for(const int &j:CB[i]) {
g<<j<<' ';
}
g<<'\n';
}
f.close();
g.close();
return 0;
}