DFS spanning tree

Question

Problem Description
Consider a Depth-First-Search(DFS) spanning tree T of a undirected connected graph G, we define a T-Simple Circle as a path v1, v2, ..., vk (v1 = vk) in G that contains at most one edge which not belongs to the DFS spanning tree T.
Given a graph G, we process DFS on G starting from vertex 1 and get a DFS spanning tree T, then you should choose some edges of G so that all T-Simple Circles contains at least one edge that you choose.
Please minimize the number of edges you choose.

Input
There are at most 100 test cases.
For each case, the first line contains two integers n and m denoting the number of vertices and edges. The vertexes are numbered from 1 to n.
The following m lines describe the graph. Each line contains two integers xi and yi, denoting an edge between vertex xi and yi(xi ≠ yi).
Note that the first n-1 edges of input construct a DFS spanning tree T which is generated by DFS from vertex 1.
Input ends with n = 0 and m = 0
(1 <= n <= 2000, 1 <= m <= 20000, 1 <= xi, yi <= n)

Output
For each case, output the number of minimal edges that you choose.

Sample Input
4 5
1 2
4 2
3 2
1 3
4 1
10 14
1 2
2 9
1 3
3 4
4 10
3 5
5 7
5 8
3 6
9 1
1 10
1 6
7 3
8 3
0 0

Sample Output
1
3

Answer 1

/*from:  https://blog.csdn.net/tmeteorj/article/details/9915247*/
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=3005,M=40005;

int ar[N];

inline int lowbit(int x){

    return x&-x;

}

int sum(int i){

    int s=0;

    for(;i>0;s+=ar[i],i-=lowbit(i));

    return s;

}

void add(int i){

    for(;i<N;ar[i]+=1,i+=lowbit(i));

}

int check(int l,int r){

    if(l>r)return 0;

    return sum(r)-sum(l-1);

}

struct Edge{

    int to,nxt;

};

struct Graph{

    int head[N],nc;

    Edge edge[M*2];

    void Init(){

        memset(head,-1,sizeof(head));

        nc=0;

    }

    void Add(int a,int b){

        edge[nc].to=b;edge[nc].nxt=head[a];head[a]=nc++;

    }

    void AddTwo(int a,int b){

        edge[nc].to=b;edge[nc].nxt=head[a];head[a]=nc++;

        edge[nc].to=a;edge[nc].nxt=head[b];head[b]=nc++;

    }

}T,G;

struct STK_Heavy{//now,fa,e,dep

    int now,fa,e,dep;

    STK_Heavy(){}

    STK_Heavy(int _n,int _f,int _e,int _d){

        now=_n,fa=_f,e=_e,dep=_d;

    }

}Hstk[N*2];

struct STK_Create{//now,ac,e

    int now,ac,e;

    STK_Create(){}

    STK_Create(int _n,int _a,int _e){

        now=_n,ac=_a,e=_e;

    }

}Cstk[N*2];

int dep[N],anc[N],pa[N],tid[N],heavy[N],size[N],ID,n,m;

bool mark[N];

void DFS_Heavy(int root){

    int top=0;

    memset(mark,false,sizeof(mark));

    Hstk[top]=STK_Heavy(root,-1,T.head[root],0);

    while(top>=0){

        STK_Heavy elem=Hstk[top];

        if(!mark[elem.now]){

            mark[elem.now]=true;

            size[elem.now]=1;

            heavy[elem.now]=-1;

            pa[elem.now]=elem.fa;

            dep[elem.now]=elem.dep;

        }

        if(elem.e==-1){

            if(top){

                size[elem.fa]+=size[elem.now];

                if(heavy[elem.fa]==-1||size[heavy[elem.fa]]<size[elem.now]){

                    heavy[elem.fa]=elem.now;

                }

            }

            top--;

            continue;

        }

        int to=T.edge[elem.e].to;

        Hstk[top].e=T.edge[elem.e].nxt;

        if(mark[to])continue;

        Hstk[++top]=STK_Heavy(to,elem.now,T.head[to],elem.dep+1);

    }

}

void DFS_Create(int root){

    int top=0;

    Cstk[0]=STK_Create(root,root,T.head[root]);

    memset(mark,false,sizeof(mark));

    while(top>=0){

        STK_Create elem=Cstk[top];

        if(!mark[elem.now]){

            mark[elem.now]=true;

            tid[elem.now]=++ID;

            anc[elem.now]=elem.ac;

            if(heavy[elem.now]!=-1){

                Cstk[++top]=STK_Create(heavy[elem.now],elem.ac,T.head[heavy[elem.now]]);

                continue;

            }

        }

        if(elem.e==-1){

            top--;

            continue;

        }

        int to=T.edge[elem.e].to;

        Cstk[top].e=T.edge[elem.e].nxt;

        if(mark[to])continue;

        Cstk[++top]=STK_Create(to,to,T.head[to]);

    }

}

bool Query(int f,int s){

    while(anc[f]!=anc[s]){

        int fs=anc[s];

        if(check(tid[fs],tid[s])!=0)return true;

        s=pa[fs];

    }

    if(f==s)return false;

    else if(check(tid[f]+1,tid[s])!=0)return true;

    else return false;

}

void Set(int f,int s){

    int p;

    while(anc[f]!=anc[s]){

        s=pa[p=anc[s]];

    }

    if(s==f){

        add(tid[p]);

    }

    else{

        add(tid[f]+1);

    }

}

void Tree_Chain(){

    memset(ar,0,sizeof(ar));

    ID=0;

    DFS_Heavy(1);

    DFS_Create(1);

}

int ans;

void dfs(int now){

    mark[now]=true;

    for(int i=T.head[now];i!=-1;i=T.edge[i].nxt){

        int to=T.edge[i].to;

        if(mark[to])continue;

        dfs(to);

    }

    for(int i=G.head[now];i!=-1;i=G.edge[i].nxt){

        int to=G.edge[i].to;

        if(!Query(now,to)){

            Set(now,to);

            ans++;

        }

    }

}

int main(){

    int a,b;

    while(scanf("%d%d",&n,&m)!=EOF){

        if(n==0&&m==0)break;

        T.Init();

        G.Init();

        for(int i=1;i<=n-1;i++){

            scanf("%d%d",&a,&b);

            T.AddTwo(a,b);

        }

        Tree_Chain();

        for(int i=n;i<=m;i++){

            scanf("%d%d",&a,&b);

            if(dep[a]>dep[b])swap(a,b);

            G.Add(a,b);

        }

        memset(mark,false,sizeof(mark));

        ans=0;

        dfs(1);

        printf("%d\n",ans);

    }

    return 0;

}