 # FAILURE - Editorial

Tester: Yash Chandnani
Editorialist: Michael Nematollahi

Medium

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

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++)
{
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++)
{
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++)
{
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++)
{
}
}

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--;
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++)
{
if(to == b_index)
continue;
}
}
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,y;
int u,v,p,d;
bool vis;
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.snd,n,m)){
repA(i,1,sz(poss)-2) ans = min(ans,poss[i].snd);
}
if(sz(poss)&&chk(poss.snd,n,m)){
ans = min(ans,poss.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];
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;
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++;
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--;
}
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;
}


Thanks for the editorial. Really builds upon intuition.

Having said that, here is my solution and TLDR:

Step 1: Does the graph have a cycle? If not print -1.
Step 2: Bridges are irrelevant. So, remove all bridges. Then each and every edge will be part of a cycle.
Step 3: Find out the vertex with most edges. If there are multiple, choose the smallest such vertex
Step 4: Delete the vertex and remove all its edges.
Step 5: Does graph still have a cycle? If so, print -1. If not, print vertex number.

10 Likes

I guess dynamic connectivity was an overkill. https://www.codechef.com/viewsolution/27781423

I think the easiest approach is this :

First let’s see bruteforce version, For all nodes from 1 to n , we remove that node and check if there is no cycle , which implies that all components of the graph are trees.

We can also check it other way round,
Total number of edges in a tree = Total number of nodes in a tree - 1

So for all components, if we remove kth node,
We get (m-degree of k) edges and n-1 nodes

If there are x number of connected components ,
then for each connected component, edge will be 1 less than the total nodes, so we get final condition : (n-1)-(m- degree of k) = x

Now coming to the final solution, we can find number of connected components we will have after removing that node by single dfs (slight modification of articulation points)

Main idea of it is : In dfs, if there is a node such that all the edges of subtree of that node dont go beyond its parent then it will be disconnected after removing the parent.

3 Likes
1. Find the first cycle [DFS], if not found print -1, if found,
2. Remove shortest vertex of the cycle and its edges.
3. Find cycle again, find the intersection of 1st and 2nd cycle [cycles so far]. If intersection does not have any nodes, print -1. Else find the shortest node from intersection and repeat from 1st step [ add the vertex which was removed earlier and its edges before finding cycle again].
4. If no cycle found, print last removed vertex.
1 Like

I used same approach.
Remove all bridges, then check maximum degree vertex is failure point or not.
https://www.codechef.com/viewsolution/27776631

Could u plz explain your approach in brief?

his solution is same as explained by nishant403 above, the difference in both solutions is that nishant used dfs to find number of connected components (assuming the vertex to be removed ) , whereas aryaman used the concept of dynamic connectivity which involves deleting and adding edges ( which tells if two nodes are in same component ) .

3 Likes

How can we prove that repeating the process multiple times won’t lead to n^2 ? Can you please explain that ?

1 Like

This can happen when all nodes are connected, But if we traverse the adjacent nodes in sorted order we would get the cycle immediately.
when N=6
we break with 2-3-4-2 [ at 4 instead of exploring 5 we explore 2 and find cycle]

I’m getting WA for this solution but I can’t find a test case for which it fails:
Keep an array cyc[N] = 0 for each node initially
Creating a DFS tree and every time I find a cycle, increment cyc[x] for each x such that it is part of the cycle
If there are cycles in the graph and there is a single node x where cyc[x] = the total number of cycles in the graph then output the smallest x, otherwise there is no single point of failure.

Can you provide the code (formatted, please )/ link to your submission?

1 Like

Hey @anon38711361, I have applied the the same approach and I also was unable to find the testcase for which it got failed. Really wonder what could have gone wrong there…

Given below is the link to my solution…

https://www.codechef.com/viewsolution/27842644

Your code fails for the testcase:

1
7 11
3 7
3 6
2 4
1 6
4 5
2 5
3 4
2 3
5 6
2 6
4 7


(the answer should be -1).

I did something kinda different, and I can’t tell if I got lucky to not get TLE…
If so, does somebody has an idea to generate a graph to make it TLE?

My idea:

I use some kind of dichotomy:
I have a stack containing intervals (initially only one: (0,N-1)).
While there is an element in it, I split my interval in two, I do a simple cycle check, forbidding to go through node of the interval.

For each interval where I get no cycle, I add them to the stack (because they can contain a point of failure). If the interval contains only one element, I return it as point of failure (it’s always the first point of failure ID, because of the way I push my intervals on stack).

For exemple, if I have 2 points of failure 2 and 4, and a graph with 5 nodes:
q=[(0,4)] => [(0,2),(3,4)] => [(2,2),(3,4)] => return 2

https://www.codechef.com/viewsolution/27774560

what is the need to find maximum degree vertex??can’t we just sort all the vertex of the cycle and check for the condition for all the vertex.

My approach was to calculate number of connected components after deleting each vertex. If after deleting a vertex, #Connected Components + #Edge = #Vertex (=N-1), then there is no cycle left and the vertex is point of failure.

This discussion helped a lot!