牛客算法周周练7 D 华华和月月逛公园 tarjan 无向图缩点

链接：https://ac.nowcoder.com/acm/contest/5713/D
来源：牛客网

题目描述
月月和华华一起去逛公园了。公园很大，为了方便，可以抽象的看成一个N个点M条边的无向连通图（点是景点，边是道路）。公园唯一的入口在1号点，月月和华华要从这里出发，并打算参观所有的景点。因为他们感情很好，走多远都不会觉得无聊，所以所有景点和道路都可以无数次的重复经过。月月发现，有些路可走可不走，有些路则必须要走，否则就无法参观所有的景点。现在月月想知道，有几条路是不一定要经过的。因为这是个很正常的公园，所以没有重边和自环。
输入描述:

第一行两个正整数N和M，表示点数和边数。
接下来M行，每行两个正整数U和V表示一条无向边。
保证给定的图是连通的。

输出描述:

输出一行一个非负整数表示不一定要经过的边有几条。

示例1
输入
复制

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

输出
复制

说明

例如第三条边，月月和华华可以依次走过第一条、第二条、第五条、第四条边走过全部的景点，所以第三条边不一定要经过。同理还有第四条、第五条边，答案为3。

备注:

1≤N≤1051\le N\le 10^51≤N≤105，1≤M≤3×1051\le M\le 3\times10^51≤M≤3×105

给定一个无向图,无重边，无自环,求经过每个点有多少条边是可以不经过的

如上图,如果有环,则环内的所有边都满足要求
所以用 $T a r j a n$ 求对每个点染色
再扫描每一条边(最后记得除以2),如果起点和终点在同一个 $S C C (强连通分量)$ 里,则这条边满足题意(
附上 $t a r j a n$ 无向图的缩点代码

vector<int> G[MAXN];
//sig表示强连通分量的个数
int dfn[MAXN], low[MAXN], timer, instk[MAXN], sig, color[MAXN];

stack<int> stk;
void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++timer;
	stk.push(u);
	instk[u] = true;
	for(auto v : G[u]) {
		if(v == fa) continue ;
		if(!dfn[v]) {
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
		} else if(instk[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if(low[u] == dfn[u]) { //发现一个强连通分量
		int x = 0;
		sig ++; //scc计数+1
		while(x != u) {
			x = stk.top(); stk.pop();
			color[x] = sig; //染色
			instk[x] = false;
		}
	}
}

完整代码如下

#define debug
#ifdef debug
#include <time.h>
#include "/home/majiao/mb.h"
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#ifdef debug
#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }
#endif

#ifndef debug
namespace FIO {
	template <typename T>
	void read(T& x) {
		int f = 1; x = 0;
		char ch = getchar();

		while (ch < '0' || ch > '9') 
			{ if (ch == '-') f = -1; ch = getchar(); }
		while (ch >= '0' && ch <= '9') 
			{ x = x * 10 + ch - '0'; ch = getchar(); }
		x *= f;
	}
};
using namespace FIO;
#endif


int n, m, Q, K;
vector<int> G[MAXN];
int dfn[MAXN], low[MAXN], timer, instk[MAXN], sig, color[MAXN];

stack<int> stk;
void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++timer;
	stk.push(u);
	instk[u] = true;
	for(auto v : G[u]) {
		if(v == fa) continue ;
		if(!dfn[v]) {
			tarjan(v, u);
			low[u] = min(low[u], low[v]);
		} else if(instk[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if(low[u] == dfn[u]) {
		int x = 0;
		sig ++;
		while(x != u) {
			x = stk.top(); stk.pop();
			color[x] = sig;
			instk[x] = false;
		}
	}
}

int main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	read(n), read(m);
	int u, v;
	for(int i=1; i<=m; i++) {
		read(u), read(v);
		G[u].push_back(v), G[v].push_back(u);
	}
	for(int i=1; i<=n; i++)
		if(!dfn[i]) tarjan(i, -1);
// forarr(color, 1, n, "color");
	int ans = 0;
	for(int i=1; i<=n; i++)
		for(int k=0; k<(int)G[i].size(); k++) {
			u = color[i], v = color[G[i][k]];
			if(u == v) ans ++;
		}
	printf("%d\n", ans/2); //答案除于二 因为无向图重复的边扫描了两次


#ifdef debug
	clock_t etime = clock();
	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
	return 0;
}