Pagini recente » Cod sursa (job #758779) | Cod sursa (job #2425106) | Cod sursa (job #1754741) | Cod sursa (job #648914) | Cod sursa (job #3223428)
#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<Edge> vert; // vert contains the edges that arrived last
int xval = 1;
void addComponent(int id, int child){
int la, lb;
r.push_back({});
while(!vert.empty() && !(la == id && lb == child) && !(la == child && lb == id)){
int a = vert.top().a, b = vert.top().b;
vert.pop();
r[r.size() - 1].push_back(a);
r[r.size() - 1].push_back(b);
la = a;
lb = b;
}
}
void dfs(int id){
if(d[id] != 0)
return;
d[id] = xval ++;
l[id] = d[id];
int minv = d[id], nrc = 0;
for(int i = 0; i < (int)v[id].size(); i ++){
if(!e[v[id][i]].solved){
int node = e[v[id][i]].getOther(id);
e[v[id][i]].solved = true;
if(d[node] == 0){
vert.push(e[v[id][i]]);
dfs(node);
nrc ++;
}
if(l[node] >= d[id]){ // Avem 1 copil care nu poate ajunge mai sus de noi
addComponent(id, node);
}
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);
}
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 < (int)r.size(); i ++){
bool f[n];
for(int j = 0; j < n; j ++)
f[j] = false;
for(int j = 0; j < (int)r[i].size(); j ++)
f[r[i][j]] = true;
for(int j = 0; j < n; j ++)
if(f[j])
fout << j + 1 << ' ';
fout << "\n";
}
fout.close();
return 0;
}