为什么要建反向图?
查看原帖
为什么要建反向图?
1088224
LittleYoo楼主2024/7/24 22:32

如题,不懂为啥要建反向图,我直接按tarjan出来的拓扑序在原图dfs就AC了,我错了吗?

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e3+5;
const int INF = 0x3fffffff;
const int mod = 100003;
#define lp(i,l,r) for(register int i=(l);i<=(r);++i)
#define rp(i,r,l) for(register int i=(r);i>=(l);--i)

vector<int> e[MAXN];
vector<int> ec[MAXN];
int dfn[MAXN], low[MAXN], scc[MAXN],  cscc, cnt;
long long siz[MAXN];
bool ins[MAXN];
stack<int> stk;

void tarjan(int p)
{
	dfn[p] = low[p] = ++cnt;
	stk.push(p);
	ins[p] = 1;
	for(auto&q:e[p]) {
		if(!dfn[q]) {
			tarjan(q);
			low[p] = min(low[p], low[q]);
		}
		else if(ins[q]) {
			low[p] = min(low[p], dfn[q]);
		}
	}	
	if(low[p] == dfn[p]) {
		int top;
		cscc++;
		do {
			top = stk.top();
			stk.pop();
			ins[top] = 0;
			scc[top] = cscc;
			siz[cscc]++;
		} while(top != p);
	}
}
bitset<MAXN> f[MAXN];
bool vis[MAXN];
void dfs(int p)
{
	vis[p] = 1;
	f[p][p] = 1;
	for(auto&q:ec[p]) {
		if(!vis[q]) {
			vis[q] = 1;
			dfs(q);
		}
		f[p] |= f[q];
	}
}
void solve()
{
	int n;
	cin >> n;
	lp(i,1,n)
		lp(j,1,n) {
			char m;
			cin >> m;
			if(m == '1')
				e[i].push_back(j);
		}

	lp(i,1,n)
		if(!dfn[i])
			tarjan(i);
	lp(u,1,n) {
		for(auto&v:e[u]) {
			if(scc[u] != scc[v]) {
				ec[scc[u]].push_back(scc[v]);
			}
		}
	}

	rp(i,cscc,1) {
		if(!vis[i]) {
			dfs(i);
		}
	}
	long long ans = 0;
	lp(i,1,cscc) {
		lp(j,1,cscc) {
			if(f[i][j]) {
				ans += siz[i] * siz[j];
			}	
		}
	}
	cout << ans << '\n';
	
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T = 1;
	// cin>>T;
	while(T--)solve();
}
2024/7/24 22:32
加载中...