牛客小白月赛12 I （tarjan求割边）

题目链接：https://ac.nowcoder.com/acm/contest/392/I

题目大意：一个含有n个顶点m条边的图，求经过所有顶点必须要经过的边数。

例：

输入：

5 5
1 2
2 3
3 4
4 5
3 5

输出：

3

解题思路：比赛的时候想的是，如果一个顶点不在环里，那与它相连的边就必定是一定要经过的边，所有可以用拓扑排序把不在环上的顶点进行统计一下，每去一个顶点必定去掉一条边，所以我们可以用总的边数减去不在环上的点的个数，不过这有个问题就是当有n个顶点，n-1条边的时候，产生的结果会是-1，开始没考虑这种情况WA了两发，我们只需要把答案和0取个最大值就好了。

然后就是出的题解用的是tarjan，显然必要的边是割边，我们用总边数减去割边数就可以了。

Tarjan做法：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn=;

int n,m,head[maxn],par[maxn],dfn[maxn],low[maxn],tot,cnt,ans;

struct node{

    int to,next;

}edge[*maxn];

void add(int u,int v){

    edge[tot].to=v;

    edge[tot].next=head[u];

    head[u]=tot++;

}

void Tarjan(int u){

    dfn[u]=low[u]=++cnt;

    for(int i=head[u];i!=-;i=edge[i].next){

        int v=edge[i].to;

        if(!dfn[v]){

            par[v]=u;

            Tarjan(v);

            if(low[v]>dfn[u]) ans++;

            low[u]=min(low[u],low[v]);

        }

        else if(v!=par[u]) low[u]=min(low[u],dfn[v]);

    }

}

int main(){

    cin>>n>>m;

    for(int i=;i<=n;i++)head[i]=-;

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

        int u,v;

        cin>>u>>v;

        add(u,v);

        add(v,u);

    }

    Tarjan();

    cout<<m-ans<<endl;

    return ;

}

拓扑做法：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<vector>

#include<string>

#include<set>

#include<cmath>

#include<list>

#include<deque>

#include<cstdlib>

#include<bitset>

#include<stack>

#include<map>

#include<queue>

using namespace std;

typedef long long ll;

#define lson l,mid,rt<<1

#define rson mid+1,r,rt<<1|1

#define pushup() tree[rt]=tree[rt<<1]+tree[rt<<1|1]

const int INF=0x3f3f3f3f;

const double PI=acos(-1.0);

const double eps=1e-;

const ll mod=;

const int maxn=;

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

const int dir[][]={{,},{-,},{,},{,-}};

int n,m,in[],sum;

vector<int> mp[];

void topsort(){

    queue<int> que;

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

        if(in[i]==){

            que.push(i); sum++;

        }

    }

    while(que.size()){

        int u=que.front();

        que.pop();

        int size=mp[u].size();

        for(int i=;i<size;i++){

            int v=mp[u][i];

            in[v]--;

            if(in[v]==){

                que.push(v);

                sum++;

            }

        }

    }

}

int main(){

    cin>>n>>m;

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

        int u,v;

        scanf("%d%d",&u,&v);

        mp[u].push_back(v);

        mp[v].push_back(u);

        in[u]++; in[v]++;

    }

    topsort();

    int ans=max(m-sum,);

    cout<<ans<<endl;

    return ;

}