Pagini recente » Cod sursa (job #1872691) | Cod sursa (job #2329233) | Cod sursa (job #2439083) | Cod sursa (job #426368) | Cod sursa (job #3223372)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define MAXN 100000
#define MAXM 200000
#define DEBUG 0
using namespace std;
struct Edge{
int a, b;
bool solved = false;
int getOther(int id){
if(id == b)
return a;
return b;
}
};
vector<vector<int>> v;
Edge e[MAXM];
vector<vector<int>> r;
int d[MAXN], l[MAXN];
stack<int> vert;
int xval = 1;
void addComponent(int idp){
r.push_back({});
while(vert.top() != idp){
r[r.size() - 1].push_back(vert.top());
vert.pop();
}
r[r.size() - 1].push_back(vert.top());
}
int dfs(int id){
if(DEBUG)
printf("%d %d %d\n", id + 1, d[id], l[id]);
if(d[id] != 0)
return 0;
d[id] = xval ++;
l[id] = d[id];
vert.push(id);
int minv = d[id], nrc = 0;
for(int i = 0; i < v[id].size(); i ++){
if(!e[v[id][i]].solved){
int node = e[v[id][i]].getOther(id);
e[v[id][i]].solved = true;
nrc += dfs(node);
if(l[node] >= d[id]){ // Avem 1 copil care nu poate ajunge mai sus de noi
addComponent(id);
}
else if(l[node] < minv) // Avem 1 copil prin care putem ajunge si mai sus
minv = l[node];
}
}
l[id] = minv;
// if(id == 0 && nrc > 1)
// addComponent(0);
return 1;
}
int main(){
int n, m;
ifstream fin ("biconex.in");
fin >> n >> m;
v.resize(n);
for(int i = 0; i < m; i ++){
int a, b;
fin >> a >> b;
e[i] = {a - 1, b - 1};
v[a - 1].push_back(i);
v[b - 1].push_back(i);
}
fin.close();
dfs(0);
ofstream fout ("biconex.out");
fout << r.size() << "\n";
for(int i = 0; i < r.size(); i ++){
for(int j = 0; j < r[i].size(); j ++)
fout << r[i][j] + 1 << " ";
fout << "\n";
}
fout.close();
return 0;
}