I've been solving some problem about DFS applications, this is the first one I do working with directed graphs. First I established that the following conditions should be enough for a graph to be a cactus, after doing a DFS and getting the DFS tree:
- DFS tree should contain all node
- There are no cross edges or forward edges
- No edge is a bridge, so every edge in the tree, has a back edge covering it
- Back edges don't intersect (no edge is covered by two back edges) and they don't overlap.
- Every node with two or more sons (except the root) should have a back edge starting in it.
- Previous conditions are enough for the graph to be Strongly connected.
However I'm getting WA, could it be an implementation mistake? or some error in the conditions I've assumed?
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define MAXN 10000
#define MAXE 10000
int E,to[MAXE],nxt[MAXE],last[MAXN];
void add_edge(int u, int v){
to[E] = v; nxt[E] = last[u]; last[u] = E++;
}
int n,cont,parent[MAXN],level[MAXN],sons[MAXN],back[MAXN];
bool done[MAXN],forward,cross;
void dfs(int pos, int lvl){
level[pos] = lvl;
sons[pos] = 0;
++cont;
for(int e = last[pos];e != -1;e = nxt[e]){
int x = to[e];
if(done[x]) cross = true;
else if(parent[x] != -1){
if(level[x] > level[pos]) forward = true;
else back[pos] = (back[pos] == -1? level[x] : -2);
}else{
parent[x] = pos;
++sons[pos];
dfs(x,lvl + 1);
}
}
done[pos] = true;
}
bool is_cactus(){
if(cont < n || forward || cross) return false;
for(int i = 0;i < n;++i)
if(back[i] == -2) return false;
for(int i = 0;i < n;++i)
if(i != 0 && sons[i] > 1 && back[i] == -1)
return false;
for(int i = 0;i < n;++i){
if(sons[i] == 0){
int e = level[i],pos = i;
while(pos != 0){
if(level[pos] == e){
if(back[pos] == -1) return false;
e = back[pos];
}else if(back[pos] != -1) return false;
pos = parent[pos];
}
}
}
return true;
}
int main(){
int T,m;
scanf("%d",&T);
while(T--){
scanf("%d %d",&n,&m);
memset(last,-1,sizeof last);
E = 0;
for(int i = 0,u,v;i < m;++i){
scanf("%d %d",&u,&v);
add_edge(u,v);
}
memset(back,-1,sizeof back);
memset(parent,-1,sizeof parent);
memset(done,false,sizeof done);
forward = cross = false;
parent[0] = -2;
cont = 0;
dfs(0,0);
puts(is_cactus()? "YES" : "NO");
}
return 0;
}
It's a tricky problem, I can't seem to see any problem with your solution. My solution for this problem is very simple.
first you see if it is a SCC.
then you run 1 dfs, with vectors seen[], and finished[]. What you are looking for is if a the dfs reaches a finished node, that would mean that that some edge takes part in more than one cicle, and it is not a cactus. Because we know every node is in a cicle, and if we reach a finished node, we ca "re-use" part of the cicle from that node and make a new cicle using the same edge, it is not easy to convince yourself of this, but if you make a few drawings, you will see.
if you like I can post my code.