文章目錄

• NC20603 [ZJOI2007]最大半連通子圖
• • 題目：
  • 題解：
  • 代碼：
• NC50403 嗅探器
• • 題目：
  • 題解：
  • 代碼：
• NC51269 Network of Schools
• • 題目：
  • 題解：
  • 代碼：
• NC106972 Cow Ski Area
• • 題目：
  • 題解：
  • 代碼：
• NC51307 Redundant Paths
• • 題目：
  • 題解：
  • 代碼：
• NC20099 [HNOI2012]礦場搭建
• • 題目：
  • 題解：
  • 代碼：
• NC19981 [HAOI2010]軟件安裝
• • 題目：
  • 題解：
• NC51267 Knights of the Round Table
• • 題目：
  • 題解：
• poj1515 NC106112 Street Directions
• • 題目：
  • 題解：
• NC51319 King's Quest
• • 題目：
  • 題解：
  • 代碼：

NC20603 [ZJOI2007]最大半連通子圖

題目：

? 一個有向圖G=(V,E)稱為半連通的(Semi-Connected)，如果滿足：u,v∈V，滿足u→v或v→u，即對于圖中任意 兩點u，v,存在一條u到v的有向路徑或者從v到u的有向路徑。
? 若G’=(V’,E’)滿足V’∈V，E’是E中所有跟V’有關的邊， 則稱G’是G的一個導出子圖。
? 若G’是G的導出子圖，且G’半連通，則稱G’為G的半連通子圖。
? 若G’是G所有半連通子圖 中包含節點數最多的，則稱G’是G的最大半連通子圖。
? 給定一個有向圖G，請求出G的最大半連通子圖擁有的節點數K ，以及不同的最大半連通子圖
的數目C。由于C可能比較大，僅要求輸出C對X的余數。

題解：

? 如果兩點互相可以到達，那么它們必是半連通圖，所以考慮先Tarjan縮點，接著去除重邊重新建圖，你會發現，在這個有向無環圖（DAG）中，半連通子圖都是一條鏈（可以舉反例試試，這條鏈不可能有分支，否則將有兩點無法抵達另一方）
? 于是，G的最大半連通子圖擁有的節點數K就是最長鏈長度，不同的最大半連通子圖的數目就是最長鏈個數。
? 最長鏈可以直接用拓撲排序（topo），最長鏈個數用一個類似DP的方法，用f【i】表示以 i為終點的方案數，那么f【i】就等于滿足距離為起點到 i 的臨時最短距離的點的 f 的和。然后查找距離等于最長鏈的點，答案為它們的方案數之和

代碼：

#include<bits/stdc++.h> using namespace std; const int maxn=1e5+10,maxm=1e6+10; struct edge {int u,v,nxt; }e[maxm],ee[maxm]; int head[maxn],js,headd[maxn],jss; void addage(edge e[],int head[],int &js,int u,int v) {e[++js].u=u;e[js].v=v;e[js].nxt=head[u];head[u]=js; } int dfn[maxn],low[maxn],cnt,st[maxn],top,lt[maxn],lts,ltn[maxn]; void tarjan(int u) {dfn[u]=low[u]=++cnt;st[++top]=u;for(int i=head[u];i;i=e[i].nxt){int v=e[i].v;if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(!lt[v])low[u]=min(low[u],dfn[v]);}if(dfn[u]==low[u]){lt[u]=++lts;ltn[lts]++;while(st[top]!=u)lt[st[top--]]=lts,ltn[lts]++;--top;} } int n,m,x; int f[maxn],ff[maxn]; int cd[maxn],rd[maxn]; int maxd,maxf; int pc[maxn]; queue<int>q; void dfs() {while(!q.empty()){int u=q.front();q.pop();maxd=max(maxd,f[u]);for(int i=headd[u];i;i=ee[i].nxt){int v=ee[i].v;rd[v]--;if(rd[v]==0)q.push(v);if(pc[v]==u)continue;if(f[u]+ltn[v]>f[v]){f[v]=f[u]+ltn[v];ff[v]=ff[u];}else if(f[u]+ltn[v]==f[v]){ff[v]=(ff[u]+ff[v])%x;}pc[v]=u;}} } int main() {scanf("%d%d%d",&n,&m,&x);for(int u,v,i=1;i<=m;++i){scanf("%d%d",&u,&v);addage(e,head,js,u,v);}for(int i=1;i<=n;++i)if(!dfn[i])tarjan(i);for(int u=1;u<=n;++u)for(int i=head[u];i;i=e[i].nxt)if(lt[e[i].u]!=lt[e[i].v])addage(ee,headd,jss,lt[e[i].u],lt[e[i].v]),cd[lt[e[i].u]]++,rd[lt[e[i].v]]++;for(int i=1;i<=lts;++i)if(rd[i]==0)q.push(i),f[i]=ltn[i],ff[i]=1;dfs();for(int i=1;i<=lts;++i){if(f[i]==maxd)maxf=(maxf+ff[i])%x;}printf("%d\n%d\n",maxd,maxf);return 0; }

NC50403 嗅探器

題目：

? 某軍搞信息對抗實戰演習，紅軍成功地侵入了藍軍的內部網絡，藍軍共有兩個信息中心，紅軍計劃在某臺中間服務器上安裝一個嗅探器，從而能夠偵聽到兩個信息中心互相交換的所有信息，但是藍軍的網絡相當的龐大，數據包從一個信息中心傳到另一個信息中心可以不止有一條通路。現在需要你盡快地解決這個問題，應該把嗅探器安裝在哪個中間服務器上才能保
證所有的數據包都能被捕獲？
輸出編號。如果有多個解輸出編號最小的一個，如果找不到任何解，輸出No solution。

題解：

? 肯定是個割點，但是割點還不夠
? 起點到終點不在同一個點雙連通分量里
? 起點到終點的路徑要經過它，且他是必經之路的第一個點——搜索

詳細講講為什么只求割點不行？如果題目給的a，b在一個連通塊里，比如圖中的2和5，我們求得1為割點，即便將1去掉，2和5依舊相連，所以我們不僅要求出割點，還要驗證這個割點能否將a和b隔開
現在我們從a開始tarjan
如果v是u的兒子，當dfn[u]<=low[v]時說明u是割點
刪掉u后，u和v必將隔開，如果b在v的一側，而a不再v的一側，這樣u不就將a和b隔開了嗎？
b在v的一側說明：dfn[b]>=dfn[v]
a在v的另一側說明：dfn[a]<dfn[v]
如果a在v的一側，b不在也是同理

代碼：

#include<bits/stdc++.h> #include<vector> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=5e5+9; vector<int>edge[maxn]; int a,b; int low[maxn],dfn[maxn]; int cnt=0; int ans=1e9; bool check(int x) {if(dfn[x]<=dfn[a]&&dfn[x]>dfn[b])return 1;if(dfn[x]<=dfn[b]&&dfn[x]>dfn[a])return 1;return 0; } void tarjan(int x,int fa) {low[x]=dfn[x]=++cnt;for(int i=0;i<edge[x].size();i++){int v=edge[x][i];if(!dfn[v]){tarjan(v,x);low[x]=min(low[v],low[x]);if(low[v]>=dfn[x]&&x!=a&&x!=b&&check(v)){ans=min(ans,x);}}else if(v!=fa)low[x]=min(low[x],dfn[v]);} } int main() {int n;cin>>n;int x,y;while(cin>>x>>y){if(x==0&&y==0)break;edge[x].push_back(y);edge[y].push_back(x);}cin>>a>>b;tarjan(a,a);if(ans==1e9)cout<<"No solution";else cout<<ans; }

NC51269 Network of Schools

題目：

給你一張有向圖，問最少要加幾條邊才能使得圖上的點都屬于同一個強連通分量

題解：

加邊變成強連通分量

縮點之后，入度為0的點和出度為0的點兩兩連邊，多隨便一連——答案就是max（入度為0的點數，出度為0的點數）

處理后：

代碼：

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=1e6+9; vector<int>edge[maxn]; int low[maxn],dfn[maxn]; int vis[maxn]; int cnt=0; stack<int>s; int num1,num2; int block; int color[maxn]; int in[maxn],out[maxn]; void tarjan(int u) {low[u]=dfn[u]=++cnt;vis[u]=1;s.push(u);for(int i=0;i<edge[u].size();i++){int v=edge[u][i];if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(vis[v])low[u]=min(low[u],dfn[v]);}int x;if(dfn[u]==low[u]){block++;do{x=s.top();s.pop();vis[x]=0;color[x]=block;}while(x!=u);} } int main() {int n;cin>>n;for(int i=1;i<=n;i++){int x;while(cin>>x){if(x==0)break;edge[i].push_back(x);}}for(int i=1;i<=n;i++){if(!dfn[i])tarjan(i);}for(int u=1;u<=n;u++){for(int i=0;i<edge[u].size();i++){int x=color[u];int y=color[edge[u][i]];if(x!=y){out[x]++;in[y]++;}}}for(int i=1;i<=block;i++){if(in[i]==0)num1++;if(out[i]==0)num2++;}if(block==1)cout<<"1"<<endl<<"0"<<endl;else printf("%d\n%d",num1,max(num1,num2)); }

NC106972 Cow Ski Area

題目：

? N*M的滑雪場，每個點都有他的高度，滑雪的時候只能向四周相鄰的不高于當前點的高度的點滑，現在滑雪場準備修建若干個纜車線路，使得奶牛可以從任意一個點運動到滑雪場的每個點，問最少需要建多少條纜車線路。

題解：

本質還是有向圖，通過加邊使其強連通
? 相鄰且高度一樣的點建雙向邊，相鄰但是高度不同的點建單向邊，然后就是上一個題了——
tarjan縮點，統計入度和出度為零的點的個數。
? 有必要建圖么？
? 相鄰且高度一樣的點在同一個連通塊里——bfs就可以縮點，沒必要tarjan

代碼：

#include<map> #include<set> #include<list> #include<stack> #include<queue> #include<vector> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm>using namespace std;const int N = 260000; int dir[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} }; int mat[550][550]; int DFN[N]; int low[N]; int block[N]; int Stack[N]; int out[N]; int in[N]; bool instack[N]; int head[N]; int tot, sccnum, index, top, n, m;struct node {int next;int to; }edge[N << 2];void addedge(int from, int to) {edge[tot].to = to;edge[tot].next = head[from];head[from] = tot++; }void tarjan(int u) {DFN[u] = low[u] = ++index;Stack[top++] = u;instack[u] = 1;for (int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if (DFN[v] == 0){tarjan(v);if (low[u] > low[v]){low[u] = low[v];}}else if (instack[v]){if (low[u] > DFN[v]){low[u] = DFN[v];}}}if (DFN[u] == low[u]){sccnum++;do{top--;block[Stack[top]] = sccnum;instack[Stack[top]] = 0;}while (Stack[top] != u);} }void solve(int ret) {memset( instack, 0, sizeof(instack) );memset( DFN, 0, sizeof(DFN) );memset( low, 0, sizeof(low) );memset( in, 0, sizeof(in) );memset( out, 0, sizeof(out) );sccnum = index = top = 0;for (int i = 0; i < ret; i++){if (DFN[i] == 0){tarjan(i);}}if(sccnum == 1){printf("0\n");return ;}for (int i = 0; i < ret; i++){for (int j = head[i]; j != -1; j = edge[j].next){if (block[i] != block[edge[j].to]){out[block[i]]++;in[block[edge[j].to]]++;}}}int a = 0, b = 0;for (int i = 1; i <= sccnum; i++){if (in[i] == 0){a++;}if (out[i] == 0){b++;}}printf("%d\n", max(a, b)); }bool is_legal(int x, int y) {if (x < 0 || x >= m || y < 0 || y >= n){return false;}return true; }int main() {while (~scanf("%d%d", &n, &m)){memset( head, -1, sizeof(head) );tot = 0;for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){scanf("%d", &mat[i][j]);}}for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){for (int k = 0; k < 4; k++){int ii = i + dir[k][0];int jj = j + dir[k][1];if ( !is_legal(ii, jj) ){continue;}if(mat[i][j] < mat[ii][jj]){continue;}else{addedge(i * n + j, ii * n + jj);}}}}solve(n * m);}return 0; }

NC51307 Redundant Paths

題目：

? 給定無向連通圖，求至少需要添加幾條邊使它變成一個邊雙連通圖。
（添多少邊可以消滅所有的橋）

題解：

先用邊雙連通縮點
? 縮點之后是一棵樹
? 無根樹的葉子（度數為1的點）都需要再添一條邊，葉子節點兩兩連接
? 答案是是（葉子數+1）/2

代碼：

這個題最坑的地方在于存在重邊，我一直被卡。。。

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } int n,m; const int maxn=1e4+9; vector<int>edge[maxn]; int low[maxn],dfn[maxn],vis[maxn]; int cnt=0; int color[maxn],block=0; stack<int>s; int out[maxn]; int iff[maxn][maxn]; void tarjan(int u,int fa) {low[u]=dfn[u]=++cnt;vis[u]=1;s.push(u);int b=0;for(int i=0;i<edge[u].size();i++){int v=edge[u][i];if(v==fa&&!b){b=1;continue;}if(!dfn[v]){tarjan(v,u);low[u]=min(low[u],low[v]);}else low[u]=min(low[u],dfn[v]);}int x;if(dfn[u]==low[u]){block++;do{x=s.top();s.pop();vis[x]=0;color[x]=block;}while(x!=u);} } int lu[maxn],lv[maxn]; int main() { // freopen("P2860_9.in","r",stdin);cin>>n>>m;for(int i=1;i<=m;i++){int u,v;cin>>u>>v;lu[i]=u;lv[i]=v;edge[u].push_back(v);edge[v].push_back(u);}for(int i=1;i<=n;i++){if(!dfn[i])tarjan(i,0);}int ans=0;for(int i=1;i<=m;i++){int u=lu[i];int v=lv[i];int x=color[u];int y=color[v];if(x!=y){out[y]++;out[x]++;}}for(int i=1;i<=block;i++){if(out[i]==1)ans++;}//ans++;cout<<(ans+1)/2; }

NC20099 [HNOI2012]礦場搭建

題目：

? 煤礦工地可以看成是由隧道連接挖煤點組成的無向圖。為安全起見，希望在工地發生事故時所有挖煤點的工人都能有一條出路逃到救援出口處。
? 于是礦主決定在某些挖煤點設立救援出口，使得無論哪一個挖煤點坍塌之后，其他挖煤點的工人都有一條道路通向救援出口。
? 請寫一個程序，用來計算至少需要設置幾個救援出口，以及不同最少救援出口的設置方案總數。

題解：

點雙連通分量的性質：

任意兩點間至少存在兩條點不重復的路徑等價于圖中刪去任意一個點都不會改變圖的連通性，即BCC中無割點

若BCC間有公共點，則公共點為原圖的割點

無向連通圖中割點一定屬于至少兩個BCC，非割點只屬于一個BCC

雙連通分量重的割點是與其他雙連通分量共享的點
? 先找割點和點雙聯通分量
? 對于一個點雙聯通分量
? 如果沒有割點——2個通道——炸了一個還有一個，方案總數就是Cn²
? 一個割點——1個通道——建在不是割點的位置，如果它坍塌了也可以從隔壁的雙連通分量里出去，方案總數就是n-1
? 兩個割點——0個——不管哪個點塌了都可以從隔壁的雙連通分量出去
本題關鍵在于dfs查找每一個連通塊內割點數量

代碼：

#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; int head[505],dfn[505],low[505],vis[505],stack[505]; bool cut[505],in_stack[505]; int n,m,cnt,num,tot,deg,ans1,T,cases,root,top; ll ans2; struct node {int from;int to;int next; }e[1010]; inline void first() {memset(head,0,sizeof(head));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(cut,0,sizeof(cut));memset(vis,0,sizeof(vis));top=cnt=tot=n=ans1=T=0; ans2=1; } inline void insert(int from,int to) {e[++num].from=from;e[num].to=to;e[num].next=head[from];head[from]=num; } inline int read() {int x=0,f=1; char c=getchar();while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while (c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; } void Tarjan(int now,int father)//求割點 {dfn[now]=low[now]=++tot;for(int i=head[now];i;i=e[i].next){int v=e[i].to;if(!dfn[v]){Tarjan(v,now);low[now]=min(low[now],low[v]);if(low[v]>=dfn[now]){if(now==root) deg++;else cut[now]=true;}}else if(v!=father) low[now]=min(low[now],dfn[v]);//不要跟求環混了 具體原理去網上找 } } void dfs(int x)//遍歷每個連通塊 {vis[x]=T;//標記 if(cut[x]) return;cnt++;//數量 for(int i=head[x];i;i=e[i].next){int v=e[i].to;if(cut[v]&&vis[v]!=T) num++,vis[v]=T;//統計割點數目。 //如果是割點且標記不與遍歷的的連通塊相同就修改標記。 if(!vis[v])dfs(v);} } int main() {m=read();while (m){first();for (int i=1;i<=m;i++){int u=read(),v=read();n=max(n,max(u,v));//這個地方要處理一下 insert(u,v); insert(v,u);}for (int i=1;i<=n;i++){if (!dfn[i]) Tarjan(root=i,0);if (deg>=2) cut[root]=1;//根節點的割點 deg=0;//不要忘記是多組數據 }for (int i=1;i<=n;i++)if (!vis[i]&&!cut[i])//不是割點 {T++; cnt=num=0;//T為連通塊的標記 dfs(i);if (!num) ans1+=2,ans2*=cnt*(cnt-1)/2;//建兩個 別忘記除以二 因為兩個建立的出口沒有差異 if (num==1) ans1++,ans2*=cnt;//建一個 }printf("Case %d: %d %lld\n",++cases,ans1,ans2);m=read();}return 0; }

NC19981 [HAOI2010]軟件安裝

題目：

? 現在我們的手頭有N個軟件，對于一個軟件i，它要占用Wi的磁盤空間，它的價值為Vi。我們希望從中選擇一些軟件安裝到一臺磁盤容量為M計算機上，使得這些軟件的價值盡可能大（即Vi的和最大）。
? 但是現在有個問題：軟件之間存在依賴關系，即軟件i只有在安裝了軟件j（包括軟件j的直接或間接依賴）的情況下才能正確工作（軟件i依賴軟件j)。幸運的是，一個軟件最多依賴另外一個軟件。如果一個軟件不能正常工作，那么它能夠發揮的作用為0。 ? 我們現在知道了軟件之間的依賴關系：軟件i依賴軟件Di。現在請你設計出一種方案，安裝價值盡量大的軟件。一個軟件只能被安裝一次，如果一個軟件沒有依賴則Di=0，這時只要這個軟件安裝了，它就能正常工作。

題解：

? 環套樹？
? 一個環上的軟件要么都裝要么都不裝
? 把環縮成點，然后建立一個虛根把所有連通塊的根都連在虛根上，樹型dp
? f[u][i]為在節點u的子樹內，費用限制為i的條件下能取到的最大價值
f[u][i]=max(f[w][j]+f[x]][k]+V[u])
x是u的兒子
j+k+W[u] = i

NC51267 Knights of the Round Table

題目：

? 一些騎士，他們有些人之間有仇恨，現在要求選出一些騎士圍成一圈，滿足如下條件：
? 人數大于1 ? 總人數為奇數
? 有仇恨的騎士不能挨著坐
? 問最少需要踢出去多少個騎士

題解：

? 能坐在一起的騎士都連邊——
? 找一個盡量大的奇環
? 注意：有可能不是簡單環
? 先求雙連通分量
? 雙連通分量里只有有一個環是奇環，那么整個環上每一點都可以在某個奇環里出現，即任意
兩點之間都有兩條長度和為奇數的路徑
? 對每個雙連通分量深搜染色即可

poj1515 NC106112 Street Directions

題目：

? 給你一張無向圖，將盡量多的邊變成定向的單向邊，讓所有的點都在一個強連通分量里面。
? 輸出任意一種方案。

題解：

? 橋——不能變成單向邊
? 其他的邊——求邊雙連通分量的時候是樹上的邊就從上到下，是返祖邊就從下到上。

NC51319 King’s Quest

題目：

N個男生和N個女生，告訴你每個男生喜歡的女生編號，然后給出一個初始匹配（這個初始匹配是一個完美匹配），求在保證匹配是完美匹配的基礎上，輸出每個男生可能會匹配的女生

題解：

參考題解：
讓我們首先來考慮建圖

如果王子u喜歡妹子v那我們可以從u向v連一條有向邊

如果妹子v可以與王子u配對（即在配對表上），那我們可以從v向u連一條有向邊

根據樣例：

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

可以得到圖

紅的是王子，藍的是妹子，綠的表示從王子到公主，黃的表示從妹子到王子

仔細觀察我們發現了這張圖的一些特別之處：

紫色部分為強連通分量
這表示在這個分量內的每個王子和這個分量內的每個妹子可以隨便匹配
所以只需要枚舉王子和他所在分量的妹子即可
tarjan，將同一強連通分量內的節點染色即可

相當于是利用完美匹配取找強連通分量
完美匹配建立反邊，所給的關系建立正邊，然后求強連通分量

代碼：

#include <bits/stdc++.h> using namespace std; const int N = 200010; struct edge {int v,nxt; }ed[N]; stack<int> st; int vis[N],head[N]; int low[N],dfn[N]; int cnt = 0,c2 = 0,c3 = 0; int a[N]; vector<int> ans[N]; void add(int u,int v) {//鏈式前向星建邊 cnt ++;ed[cnt].v = v;ed[cnt].nxt = head[u];head[u] = cnt; } void tarjan(int x) {//模板Tarjan算法 c2 ++;low[x] = dfn[x] = c2;st.push(x);//每個點進棧 vis[x] = 1;//表示這個點已進棧 for (int i = head[x];i;i = ed[i].nxt) {//遍歷每條邊 int v = ed[i].v;if (!dfn[v]) {//沒有訪問過 tarjan(v);low[x] = min(low[x],low[v]);}else if (vis[v]) {//這個點在棧里 low[x] = min(low[x],dfn[v]);}}if (low[x] == dfn[x]) {//強連通分量的根 c3 ++;int u;do{u=st.top() ;vis[u] = 0;//出棧，就去掉標記 a[u] = c3;//染色 st.pop();}while(x!=u);} }inline void write(int x) {//快速輸出 if (x > 9) write(x / 10);putchar(x % 10 + '0'); } int main() {int n;scanf("%d",&n);for (int i = 1;i <= n;i ++ ) {int t;scanf("%d",&t);//公主個數 for (int j = 1;j <= t;j ++ ) {int x;scanf("%d",&x);add(i,x + n);//王子向公主連邊，注意公主編號從n+1開始 }}for (int i = 1;i <= n;i ++ ) {int x;scanf("%d",&x);add(x + n,i);//反向，公主向王子連邊 }for (int i = 1;i <= n * 2;i ++ ) {//兩倍 if (!dfn[i]) tarjan(i);}for (int i = 1;i <= n;i ++ ) {for (int j = head[i];j;j = ed[j].nxt) {int v = ed[j].v;if (a[i] == a[v]) {//找既是喜歡又同色的公主，加入答案ans[i].push_back(v);}}sort(ans[i].begin(),ans[i].end());//一定要排序！！ }for (int i = 1;i <= n;i ++ ) {write(ans[i].size());//輸出個數 putchar(' ');for (int j = 0;j < ans[i].size();j ++ ) {write(ans[i][j] - n);//編號最后要減n putchar(' ');}putchar('\n');}return 0; }

總結

以上是生活随笔為你收集整理的连通性（相关练习）的全部內容，希望文章能夠幫你解決所遇到的問題。

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