題目描述?Description

某學(xué)校即將開展軍訓(xùn)。共有N個(gè)班級(jí)。

前M個(gè)優(yōu)秀班級(jí)為了保持學(xué)習(xí)優(yōu)勢(shì)，必須和3位任課老師帶的班級(jí)同一批。

問共有幾批？

輸入描述?Input Description

N,M

老師教的其他班級(jí)（M行）

輸出描述?Output Description

批次數(shù)

樣例輸入?Sample Input

4 2

1 1 1

2 3 1

?

樣例輸出?Sample Output

2

數(shù)據(jù)范圍及提示?Data Size & Hint

對(duì)于50%數(shù)據(jù)，N,M<=1000.

對(duì)于100%數(shù)據(jù)，N,M<=30000,N<=M.

/*迷之題意先說下題目意思吧:給定n個(gè)班級(jí)，m個(gè)優(yōu)秀班級(jí)，對(duì)于每個(gè)優(yōu)秀班級(jí)，給出3名老師，數(shù)值代表每個(gè)老師還教著哪個(gè)班。教同一個(gè)班的三名老師必須同一批次，問需要多少批次。因?yàn)榻掏粋€(gè)班的三名老師必須同一批次，所以對(duì)于每一個(gè)優(yōu)秀班級(jí)，都最多有可能有另外3個(gè)班和它同一批次，我們就用并查集將它們合并，以求出答案。 */ #include<cstdio> #include<iostream> #define M 30010 using namespace std; int fa[M]; int find(int x) {if(fa[x]==x)return x;return fa[x]=find(fa[x]); } int main() {int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)fa[i]=i;for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);int r=find(i),a=find(x),b=find(y),c=find(z);if(r!=a)fa[a]=r;if(r!=b)fa[b]=r;if(r!=c)fa[c]=r;}int ans=0;for(int i=1;i<=n;i++)if(fa[i]==i)ans++;printf("%d",ans);return 0; } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/harden/p/5707755.html

總結(jié)

以上是生活随笔為你收集整理的军训分批（codevs 2751）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。