AOJ

# # Problem

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B

# # Computational complexity

$O(V+E)$

# # Solution


#define MAX_V 10000

vector<Int> graph[MAX_V];
bool used_v[MAX_V],used_e[MAX_V][MAX_V];
Int k=0;
vector<pair<Int, Int> > bridges;

bool compare (pair<Int, Int> a, pair<Int, Int> b) {
if (a.first != b.first)  return a.first < b.first;
if (a.second != b.second) return a.second < b.second;
return false;
}

void dfs(Int v, Int parent) {
used_v[v] = true;

for (Int u: graph[v]) {
if(!used_v[u]) {
used_e[v][u] = true;
dfs(u, v);
if (v < u) bridges.push_back(make_pair(v, u));
else bridges.push_back(make_pair(u, v));
}
}
else if(!used_e[u][v]) {
}
}
}

Int main(void) {
Int n, e, u, v;
cin >> n >> e;
loop(i,0,e) {
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
dfs(0, -1);
sort(bridges.begin(), bridges.end(), compare);
for (auto b: bridges) cout << b.first << ' ' << b.second << endl;
}


Remote freelancer. A web and mobile application enginner.
Traveling around the world based on East Asia.
I'm looking forward to your job offers from all over the world!

Offer jobs or contact me!