گراف مکمل

[msh118]

برنامه‌ای بنویسید که یک گراف را از ورودی دریافت کند و مکمل آنرا نمایش دهد

توضیح:

دوتا گراف رو دریافت کنه اولی گراف کامل باشه، دومی هر گرافی میتونه باشه (اصطلاحا گراف G)بعد راس هایی که هر دوگراف با برابرن یا مشابه اند رو حذف ومابقی رو به

خروجی ببره

http://www.7khatcode.com/?qa=blob&qa_blobid=16177503593138108202

[sa1378]

#include <iostream>
#include <vector>
using namespace std;
#define N (1000)
bool mark[N];
int main()
{
int n,m,nkol; // nkol=ras haye geraf kamel n=tedad ras m=tedad yal
cin>>nkol>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
mark[a]=mark[b]=true;
}
for(int i=1;i<=nkol;i++)
{
if(mark[i]==false)
{
for(int j=1;j<=nkol;j++)
if(mark[j]==false && i!=j)
cout<<i<<" "<<j<<endl;
mark[i]=true;
}
}

return 0;
}

[msh118]

سلام با تشکر ازپاسخ تون لطف میکنید اگه راجع به کدها توضیح بیشتری دهید آخه مبتدی هستم البته تو بحث گراف ها

[sa1378]

سلام با تشکر ازپاسخ تون لطف میکنید اگه راجع به کدها توضیح بیشتری دهید آخه مبتدی هستم البته تو بحث گراف ها

اول میاد nkol رو میگیره که تعداد راس های گراف کامل اولیه ما هست
بعد میاد n,m رو میگیره که به ترتیب تعداد یالها و راس ها هستن
بعد یه حلقه هست که m بار تکرار میشه و هربار سر و ته یه یال رو میگیره
هربار که سر و ته یال رو گرفتیم میایم مارک اون راس ها رو 1 میکنیم یعنی توی گراف جوابمون نباید باشن
...
حالا که حلقه تموم شد میایم دوتا حلقه پشت سر هم میزاریم که راس هایی که مارکشون 1 نیست (یعنی توی گراف قبلی نیومدن) رو دوتادوتا به هم وصل کنه و یالشون رو نمایش بده