#include <iostream>002 using namespace std;003004 typedef struct LNode005 {006 int num;//記錄連通子集的個數007 struct LNode* head;008 struct LNode* tail;009 struct LNode* next;010 }LNode,*LinkList;011012 LNode L[101];013014 void InitLNode(int n)//初始化各個子集015 {016 for(int i=1;i<=n;i++)017 {018 L[i].num=n; //初始化連通子集個數為n019 L[i].head=&L[i];020 L[i].tail=&L[i];021 L[i].next=NULL;022 }023 }024025 LinkList FindSetNum(int n)//求代表元,以各個集合的第一個元素為代表元并返回其地址026 {027 return L[n].head;028 }029030 void SetUnion(int a,int b,int s)//合并各個子集031 {032 LinkList p;033 p=L[a].head;034 L[a].tail->next=L[b].head; //把b所在的集合的首元素與尾元素的地址分別賦給a所在的尾元素和首元素035 L[a].head->tail=L[b].tail;036 p=L[b].head;037 while(p->next!=NULL) //把b所在集合元素的頭指針指向合并之后所在的代表元038 {039 p->head=L[a].head;040 p=p->next;041 }042 if(p->next==NULL)043 p->head=L[a].head;044 for(int i=1;i<=s;i++)045 L[i].num-=1;046 }047048 bool JudgeRelation(int a,int b)//判斷兩臺電腦之間是否連接049 {050 if(FindSetNum(a)==FindSetNum(b))051 return true;052 else053 return false;054 }055056 void main()057 {058 int s,n,a;059 char m;060 while(cin>>s && s!=0)061 {062 InitLNode(s);063 while(s==1)064 {065 cout<<"The network is "<<s<<" components.\n";066 break;067 }068 while(cin>>m && (m=='C' || m=='I' || m=='S' || m=='c' || m=='s' || m=='i'))069 {070 switch(m)071 {072 case 'C':073 case 'c':074 cin>>n>>a;075 if(JudgeRelation(n,a))076 {077 cout<<"YES\n";078 }079 else080 {081 cout<<"NO\n";082 }083 break;084 case 'I':085 case 'i':086 cin>>n>>a;087 if(!JudgeRelation(n,a))088 SetUnion(n,a,s);089 break;090 }091 if(m=='S' || m=='s')092 {093 if(L[1].num==1)094 {095 cout<<"The network is connected.\n";096 }097 else098 {099 cout<<"The network is "<<L[1].num<<" components.\n";100 }101 break;102 }103 }104 }105 }
2 回答
桃花長相依
TA貢獻1860條經驗 獲得超8個贊
#include <stdio.h>#define bool char#define true 1#define false 0 typedef struct LNode{ int num;//記錄連通子集的個數 struct LNode* head; struct LNode* tail; struct LNode* next;}LNode,*LinkList; LNode L[101]; void InitLNode(int n)//初始化各個子集{ int i; for(i=1;i<=n;i++) { L[i].num=n; //初始化連通子集個數為n L[i].head=&L[i]; L[i].tail=&L[i]; L[i].next=NULL; }} LinkList FindSetNum(int n)//求代表元,以各個集合的第一個元素為代表元并返回其地址{ return L[n].head;} void SetUnion(int a,int b,int s)//合并各個子集{ int i; LinkList p; p=L[a].head; L[a].tail->next=L[b].head; //把b所在的集合的首元素與尾元素的地址分別賦給a所在的尾元素和首元素 L[a].head->tail=L[b].tail; p=L[b].head; while(p->next!=NULL) //把b所在集合元素的頭指針指向合并之后所在的代表元 { p->head=L[a].head; p=p->next; } if(p->next==NULL) p->head=L[a].head; for(i=1;i<=s;i++) L[i].num-=1;} bool JudgeRelation(int a,int b)//判斷兩臺電腦之間是否連接{ if(FindSetNum(a)==FindSetNum(b)) return true; else return false;} void main(){ int s,n,a; char m; while(scanf("%d", &s) && s!=0) { InitLNode(s); while(s==1) { printf("The network is %d components.\n", s); break; } while(scanf("%c", &m) && (m=='C' || m=='I' || m=='S' || m=='c' || m=='s' || m=='i')) { switch(m) { case 'C': case 'c': scanf("%d%d", &n, &a); if(JudgeRelation(n,a)) { printf("YES\n"); } else { printf("NO\n"); } break; case 'I': case 'i': scanf("%d%d", &n, &a); if(!JudgeRelation(n,a)) SetUnion(n,a,s); break; } if(m=='S' || m=='s') { if(L[1].num==1) { printf("The network is connected.\n"); } else { printf("The network is %d components.\n",L[1].num); } break; } } }} |
慕田峪7331174
TA貢獻1828條經驗 獲得超13個贊
cin改成scanf形式
cout改成printf形式
bool改成int
true改成1，false改成0
頭文件改成#include<stdio.h>
去掉using namespace std;
- 2 回答
- 0 關注
- 129 瀏覽
添加回答
舉報
0/150
提交
取消