PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Erfan Alimohammadi
Tester: Yash Chandnani
Editorialist: Michael Nematollahi
DIFFICULTY:
Medium
PREREQUISITES:
DFS Tree
PROBLEM:
You are given a simple graph with N nodes and M edges.
If the graph contains a cycle and there is a vertex v such that removal of v would result in a graph with no cycles, you have to print the label of v. Otherwise print -1.
The vertices satisfying the mentioned requirement are called critical.
If there are multiple critical vertices, print the one with the minimum label.
QUICK EXPLANATION:
Run a dfs on the graph and consider the resulting tree. For a vertex v to be critical, it needs to be on the “tree-path” of every “off-tree-edge”. Additionally, there should be at most one “off-tree-edge” coming out of each subtree of v that goes above v.
It can be proven that these two conditions are necessary and sufficient conditions for v to be critical. The conditions can be checked for all vertices via a dfs traversal of the graph, which would run in O(N+M).
EXPLANATION:
Without loss of generality, we assume in this editorial that the graph is connected. The same solution can easily be extended to disconnected graphs.
We start by running a dfs on the graph, which would result in a dfs tree. We’ll refer to this tree as simply “the tree”.
Let a “back-edge” be an edge of the original graph that is not part of the tree and is between a vertex v and one of the ancestors of v.
Fact 1: Every edge of the original graph that is not part of the tree is a back-edge.
This is one of the properties of a dfs tree that we will not prove in this editorial.
Let totExtra be the number of back-edges in the tree. It’s easy to see that if totExtra = 0, there are no cycles in the graph and thus the answer is -1. From now on we assume totExtra \neq 0.
We claim that the conditions below are necessary and sufficient for a vertex v to be critical.
-
Condition 1: v should lie on the “tree-path” (the path connecting two vertices in the tree) of the endpoints of every back-edge.
-
Condition 2: There should be no subtree S of v such that there are two back-edges from S that go above v in the tree (assuming that the tree is hanging down from the root).
Now we argue why these conditions are necessary.
If condition 1 does not hold, there exists a back-edge x-y such that v does not lie on the tree-path of x and y. Hence, after removing v, the graph still contains the cycle composed of the tree-path of x and y and the edge x-y. Therefore, condition 1 is necessary for v to be critical.
If condition 2 does not hold, there exist a subtree S of v and two distinct edges a-b and c-d (note that these don’t have to be four distinct vertices) such that a, c \in S and b, d \in anc(v) (where anc(v) denotes the set of ancestors of v, excluding v). Hence, after removing v from the graph, there still exists a cycle composed of the tree-path of a and c and the tree-path of b and d and the edges a-b and c-d. Therefore, condition 2 is necessary for v to be critical.
Now, we argue that these conditions are sufficient for v to be critical.
After removing v from the graph, the tree would be divided up into possibly several components (each of which would be a tree). By condition 1, there will be no back-edge in each of these components. In other words, these components will be trees even if we add all the edges in the original graph to them.
On the other hand, because the graph edges were decomposed into tree-edges and back-edges, and by condition 1, we know that all remaining “off-tree-edges” are between anc(v) and subtrees of v. Also, by condition 2, we know that each subtree of v has at most one edge to anc(v). So if we consider each component of the resulting graph to be a vertex, the graph formed by “off-tree-edges” will be a “star”. This means that there will be no cycles in the resulting graph, hence v is critical.
Now, it’s time to figure out how to actually implement an approach to check these conditions for all vertices in a “quick-enough” manner. There are possibly several ways to do this. Here, we do it using a modified dfs algorithm.
Keeping track of back-edges can be done using a colouring plan like the one described here:
To check condition 2, we make dfs(v) return the depth of the two highest edges from subtree of v. To see how this idea can be used to determine if condition 2 is satisfied, refer to the editorialist’s code. In the code, hasPotential[v] denotes whether or not condition 2 is satisfied for v.
To check condition 1, for very back edge v-u, where u is an ancestor of v, we increment sm[v] and decrement sm[par[u]]. This way, the number of back-edges whose tree-paths contains a vertex x is equal to the sum of sm[y] for all y in the subtree of x. A fairly similar method is implemented in the editorialist’s code.
The overall complexity is the complexity of a DFS algorithm, which is O(N+M).
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005
vector<int> adj[MAXN];
vector<int> after_adj[MAXN];
bool visited[MAXN];
int col[MAXN];
int tin[MAXN];
int low[MAXN];
int deg[MAXN];
int timer;
void dfs(int v, int p = -1)
{
visited[v] = true;
tin[v] = low[v] = timer++;
for (int i = 0; i < (int)adj[v].size(); i++)
{
int to = adj[v][i];
if (to == p) continue;
if (visited[to])
low[v] = min(low[v], tin[to]);
else {
dfs(to, v);
low[v] = min(low[v], low[to]);
if (low[to] > tin[v])
{
deg[to]--;
deg[v]--;
}
}
}
}
void find_bridges(int n)
{
timer = 0;
memset(visited, false, sizeof visited);
memset(tin, -1, sizeof tin);
memset(low, -1, sizeof low);
for (int i = 0; i < n; ++i) {
if (!visited[i])
dfs(i);
}
}
bool pre_cycle(int u, int par = -1)
{
bool res = false;
col[u] = 1;
for(int i = 0; i < (int)adj[u].size(); i++)
{
int v = adj[u][i];
if(v == par)
continue;
if(col[v] == 2)
continue;
if(col[v] == 1)
res = true;
else res |= pre_cycle(v, u);
}
col[u] = 2;
return res;
}
bool post_cycle(int u, int par = -1)
{
bool res = false;
col[u] = 1;
for(int i = 0; i < (int)after_adj[u].size(); i++)
{
int v = after_adj[u][i];
if(v == par)
continue;
if(col[v] == 2)
continue;
if(col[v] == 1)
res = true;
else res |= post_cycle(v, u);
}
col[u] = 2;
return res;
}
void init()
{
memset(deg, 0, sizeof deg);
timer = 0;
for(int i = 0; i < MAXN; i++)
{
adj[i].clear();
after_adj[i].clear();
}
}
int main()
{
int t;
cin >> t;
// cerr << "Read number of tests" << endl;
while(t--)
{
init();
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++)
{
int u, v;
cin >> u >> v;
u--;
v--;
adj[u].push_back(v);
adj[v].push_back(u);
deg[u]++;
deg[v]++;
}
// cerr << "Read graph" << endl;
int cnt = 0;
memset(col, 0, sizeof col);
// cerr << "Starting Cycle Check" << endl;
for(int i = 0; i < n; i++)
{
if(col[i] == 0)
{
if(pre_cycle(i))
cnt++;
}
}
// cerr << "Cycle Checked" << endl;
if(cnt > 1)
{
cout << "-1" << endl;
continue;
}
if(cnt == 0)
{
cout << "-1" << endl;
continue;
}
find_bridges(n);
// cerr << "found bridges" << endl;
int best = -1, b_index = -1;
for(int i = 0; i < n; i++)
{
if(deg[i] > best)
{
best = deg[i];
b_index = i;
}
}
// remove b_index from graph
for(int i = 0; i < n; i++)
{
if(i == b_index)
continue;
for(int j = 0; j < (int)adj[i].size(); j++)
{
int to = adj[i][j];
if(to == b_index)
continue;
after_adj[i].push_back(to);
}
}
cnt = 0;
memset(col, 0, sizeof col);
for(int i = 0; i < n; i++)
{
if(col[i] == 0)
{
if(post_cycle(i))
cnt++;
}
}
if(cnt > 0)
cout << "-1" << endl;
else
cout << b_index + 1 << endl;
// cerr << "finished" << endl;
}
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repA(i, a, n) for(int i = a; i <= (n); ++i)
#define repD(i, a, n) for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a) memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
void pre(){
}
vector<vi> g;
int x[100009],y[100009];
int u[100009],v[100009],p[100009],d[100009];
bool vis[100009];
void dfs(int u,int v){
p[u] = v;
vis[u] = 1;
if(v!=-1) d[u]=d[v]+1;
trav(i,g[u]){
if(!vis[i]) dfs(i,u);
}
}
void dfs2(int u){
vis[u] = 1;
trav(i,g[u]){
if(!vis[i]){
dfs2(i);
x[u] += x[i]-y[i];
}
}
}
struct UF {
vi e;
UF(int n) : e(n, -1) {}
bool same_set(int a, int b) { return find(a) == find(b); }
int size(int x) { return -e[find(x)]; }
int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
void join(int a, int b) {
a = find(a), b = find(b);
if (a == b) return;
if (e[a] > e[b]) swap(a, b);
e[a] += e[b]; e[b] = a;
}
};
bool chk(int x,int n,int m){
UF dsu(n);
rep(i,m) if(u[i]!=x&&v[i]!=x){
if(dsu.find(u[i])==dsu.find(v[i])) return 0;
dsu.join(u[i],v[i]);
}
return 1;
}
void solve(){
int n,m;cin>>n>>m;
g.clear();
g.resize(n);
fill(x);
fill(y);
fill(vis);
rep(i,m) {
cin>>u[i]>>v[i];
u[i]--,v[i]--;
g[u[i]].pb(v[i]);
g[v[i]].pb(u[i]);
}
rep(i,n) if(!vis[i]) dfs(i,-1);
int cnt = 0;
rep(i,m){
if(p[u[i]]==v[i]||p[v[i]]==u[i]) {}
else{
cnt++;
if(d[u[i]]<d[v[i]]) swap(u[i],v[i]);
x[u[i]]++;
y[v[i]]++;
}
}
if(cnt==0){
cout<<-1<<'\n';
return;
}
fill(vis);
rep(i,n) if(!vis[i]) dfs2(i);
vector<pii> poss;
rep(i,n){
if(x[i]==cnt) {
poss.pb({d[i],i});
}
}
sort(all(poss));
int ans = n;
if(sz(poss)>1&&chk(poss[1].snd,n,m)){
repA(i,1,sz(poss)-2) ans = min(ans,poss[i].snd);
}
if(sz(poss)&&chk(poss[0].snd,n,m)){
ans = min(ans,poss[0].snd);
}
if(sz(poss)&&chk(poss.back().snd,n,m)){
ans = min(ans,poss.back().snd);
}
if(ans==n) cout<<-1<<'\n';
else cout<<ans+1<<'\n';
}
int main() {
cin.sync_with_stdio(0); cin.tie(0);
cin.exceptions(cin.failbit);
pre();
int n;cin>>n;
rep(i,n) {
solve();
}
return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
const int MAXN = 1e5 + 10;
const int INF = 1e9;
int n, m, totExtra, cntAdj[MAXN], sm[MAXN], hasPotential[MAXN], depth[MAXN];
vector<int> adj[MAXN];
int vis[MAXN];
void update(pii &p, int x){
if (p.S > x)
p.S = x;
if (p.F > p.S)
swap(p.F, p.S);
}
pii dfs(int v, int p = -1, int de = 0){
pii ret(INF, INF);
depth[v] = de;
vis[v] = 1;
hasPotential[v] = 1;
for (int u: adj[v])
if (u^p)
if (!vis[u]) {
auto x = dfs(u, v, de + 1);
sm[v] += sm[u];
update(ret, x.S);
update(ret, x.F);
if (x.S < de)
hasPotential[v] = 0;
}
else if (vis[u] == 1){
totExtra++;
cntAdj[v]++;
cntAdj[u]++;
sm[p]++;
sm[u]--;
update(ret, depth[u]);
}
vis[v] = 2;
return ret;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int te; cin >> te;
while (te--){
cin >> n >> m;
for (int i = 0; i < n; i++) adj[i].clear(), cntAdj[i] = sm[i] = 0;
while (m--){
int u, v; cin >> u >> v, u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
memset(vis, 0, sizeof(vis));
totExtra = 0;
for (int v = 0; v < n; v++)
if (!vis[v])
dfs(v);
if (totExtra == 0){
cout << "-1\n";
continue;
}
int ans = -1;
for (int v = 0; ans == -1 && v < n; v++)
if (cntAdj[v] + sm[v] == totExtra && hasPotential[v])
ans = v+1;
cout << ans << "\n";
}
return 0;
}