奇怪的缩点做法,不懂为啥错了
  • 板块题目总版
  • 楼主Exile_Code
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/7/15 18:41
  • 上次更新2024/7/15 19:43:54
查看原帖
奇怪的缩点做法,不懂为啥错了
819682
Exile_Code楼主2024/7/15 18:41
#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <map>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <string>
#include <cmath>
#include <bitset>
#include <stack>
#include <math.h>
#include <functional>
#include <numeric>

#define int                long long
#define endl            '\n'
#define ull             unsigned long long 
#define ll              long long 
#define pii             pair<int,int>
#define cy              cout<<"Yes"<<'\n'
#define cn              cout<<"No"<<'\n'
#define forn(i,begin,end,add)    for(ll (i)=(begin);(i)<=(end);(i)+=(add))    //begin是i的起始,end是i的终止,add是每次加的大小
#define rforn(i,begin,end,sub)  for(ll (i)=(end);(i)>=(begin);(i)-=(sub))    //r是倒序遍历
#define vv              vector
#define inf32           INT32_MAX/2
#define inf64           INT64_MAX/2
#define LD              long double
#define PI              acos(-1)
#define debug(a,b)        cout<<a<<b
#define eps                1e-12 
const int N = 4e5 + 100;
ll T;

const ll mod = 1e9 + 7;


int t = 1;

int tot = 0;//编号
int cnt;//强连通图的编号
vv<int> dfn;//节点x第一次被访问的顺序
vv<int> low;//从节点x出发,所能访问到的最早时间戳
vv<int> instk;//是否在栈中

vv<int> siz;//强连通分量的大小
vv<int> scc;//某一个点在哪一个强连通分量中
vv<vv<int>>e;

//割点
int root;
vv<int>cut;

void init(int n, int rt) {
	cnt = 0, tot = 0;
	e = vv<vv<int>>(n + 1, vv<int>());
	dfn = low = vv<int>(n + 1);
	instk = vv<int>(n + 1);

	//割点 
	int root = rt;
	cut = vv<int>(n + 1);

}
void tarjan(int x) {
	dfn[x] = low[x] = ++tot;
	instk[x] = true;

	for (int y : e[x]) {
		//if(y==x) 出现自环
		if (!dfn[y]) {
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if (instk[y]) {//y还没往下走,所以用dfn更新
			low[x] = min(low[x], dfn[y]);
		}
		//如果一个点既不在栈中,又已经走过了,不需要再走了,因为横跨边无法更新任何东西
	}
	
}

void solve() {

	int n; cin >> n;
	init(n, 1);
	
	vv<int>du(n + 1);
	
	forn(i, 1, n, 1) {
		int a; cin >> a;
		e[a].push_back(i);
		du[i]++;
	}


	int ans = 0;
	forn(i, 1, n, 1) //第一遍处理有入边的环和单点
		if (!dfn[i] && du[i] == 0)
			ans++, tarjan(i);

	forn(i, 1, n, 1)//第二遍处理所有没有入边的环
		if (!dfn[i])
			ans++, tarjan(i);


	cout << ans << endl;
	


}
signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

   
   // cin >> t;

    while (t--)
        solve();

    return 0;
}
2024/7/15 18:41
加载中...