題目描述

給定一張有向圖，求從1號點出發，每個點能支配的點的個數（包括自己）

輸入輸出格式

輸入格式：

第一行兩個正整數n,mn,m，表示點數和邊數 接下來mm行，每行輸入兩個整數u,vu,v，表示有一條uu到vv的有向邊

輸出格式：

一行輸出nn個整數，表示每個點能支配的點的個數

輸入輸出樣例

輸入樣例#1：

10 15
1 2
2 3
3 4
3 5
3 6
4 7
7 8
7 9
7 10
5 6
6 8
7 8
4 1
3 6
5 3

輸出樣例#1：

10 9 8 4 1 1 3 1 1 1?

思路：求一般有向圖的支配點，支配樹的 Lengauer Tarjan 算法模板題

源代碼

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<unordered_map> #include<bitset> #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<LL,LL> LL quickPow(LL a,LL b){ LL res=1; while(b){if(b&1)res*=a; a*=a; b>>=1;} return res; } LL quickModPow(LL a,LL b,LL mod){ LL res=1; a=a%mod; while(b){if(b&1)res=(a*res)%mod; a=(a*a)%mod; b>>=1;} return res; } LL getInv(LL a,LL mod){ return quickModPow(a,mod-2,mod); } LL GCD(LL x,LL y){ return !y?x:GCD(y,x%y); } LL LCM(LL x,LL y){ return x/GCD(x,y)*y; } const double EPS = 1E-10; const int MOD = 998244353; const int N = 400000+5; const int dx[] = {-1,1,0,0,1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;struct MAP {struct Edge {int to, next;} edge[N << 1];int tot, head[N];void addEdge(int x, int y) {edge[++tot].to = y;edge[tot].next = head[x];head[x] = tot;} }; MAP G, GF; //原圖、反圖 MAP dfsTree, dfsTreeF; // dfs樹、dfs樹的反圖 MAP dominate; //支配樹MAP xx; int n, m; int father[N]; // dfs樹上的父節點 int dfn[N], id[N], tim; // dfs序、標號、時間戳void dfs(int x) {id[++tim] = x;dfn[x] = tim;for (int i = G.head[x]; i; i = G.edge[i].next) {int to = G.edge[i].to;if (!dfn[to]) {dfs(to);father[to] = x;dfsTree.addEdge(x, to);}} }int sdom[N]; //半支配點 int mn[N]; // mn[i]表示i點的dfs樹上的sdom最小的祖先,因此有sdom[mn[i]]=sdom[i] int anc[N]; // anc[i]代表i的祖先 int find(int x) { //路徑壓縮的帶權并查集if (x != anc[x]) {int t = anc[x];anc[x] = find(anc[x]);if (dfn[sdom[mn[x]]] > dfn[sdom[mn[t]]])mn[x] = mn[t];}return anc[x]; } void LengauerTarjan() { //尋找半支配點for (int i = 1; i <= n; i++) {anc[i] = i;sdom[i] = i;mn[i] = i;}for (int j = n; j >= 2; j--) {int x = id[j];if (!x)continue;int pos = j;for (int i = GF.head[x]; i; i = GF.edge[i].next) {int y = GF.edge[i].to;if (!dfn[y])continue;if (dfn[y] < dfn[x])pos = min(pos, dfn[y]);else {find(y); //尋找樹上y的一個滿足dfn[z]>dfn[x]的祖先zpos = min(pos, dfn[sdom[mn[y]]]);}}sdom[x] = id[pos];anc[x] = father[x];dfsTree.addEdge(sdom[x], x); //在dfs樹上連邊} }int deep[N], dp[N][25]; int getLCA(int x, int y) { //獲取LCAif (deep[x] < deep[y])swap(x, y);int del = deep[x] - deep[y];for (int i = 0; i <= 20; i++)if ((1 << i) & del)x = dp[x][i];if (x == y)return x;for (int i = 20; i >= 0; i--) {if (dp[x][i] != dp[y][i]) {x = dp[x][i];y = dp[y][i];}}return dp[x][0]; } void buildDominate(int x) { //建立支配樹int to = dfsTreeF.edge[dfsTreeF.head[x]].to;for (int i = dfsTreeF.head[x]; i; i = dfsTreeF.edge[i].next) {int y = dfsTreeF.edge[i].to;to = getLCA(to, y);}deep[x] = deep[to] + 1;dp[x][0] = to;dominate.addEdge(to, x);for (int i = 1; i <= 20; i++)dp[x][i] = dp[dp[x][i - 1]][i - 1]; } int in[N]; // dfs樹的入度 void topSort() {for (int i = 1; i <= n; i++) {for (int j = dfsTree.head[i]; j; j = dfsTree.edge[j].next) {int to = dfsTree.edge[j].to;in[to]++;dfsTreeF.addEdge(to, i); //對DFS樹的反圖建邊}}for (int i = 1; i <= n; i++) {if (!in[i]) {dfsTree.addEdge(0, i); // dfs樹建邊dfsTreeF.addEdge(i, 0); // dfs樹的反圖建邊}}queue<int> Q;Q.push(0);while (Q.size()) {int x = Q.front();Q.pop();for (int i = dfsTree.head[x]; i; i = dfsTree.edge[i].next) {int y = dfsTree.edge[i].to;if ((--in[y]) <= 0) {Q.push(y);buildDominate(y); //建立支配樹}}} }int idom[N]; void dfsDominate(int x) { //在支配樹上搜索idomidom[x] = 1;for (int i = dominate.head[x]; i; i = dominate.edge[i].next) {int y = dominate.edge[i].to;dfsDominate(y);idom[x] += idom[y];} } int main() {scanf("%d%d", &n, &m);for (int i = 1; i <= m; i++) {int x, y;scanf("%d%d", &x, &y);G.addEdge(x, y);GF.addEdge(y, x);}dfs(1); // dfs，求出dfs序LengauerTarjan(); //計算半支配點sdomtopSort(); //根據dfs樹建立dfs樹的反圖，并對進行拓撲排序從而建立支配樹dfsDominate(0); //在支配樹上尋找答案for (int i = 1; i <= n; i++)printf("%d ", idom[i]);printf("\n");return 0; }

?

總結

以上是生活随笔為你收集整理的支配树（洛谷-P5180）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。