اینی که میگی topological sort میگن بش ، که راس ها رو یه جور میچینه که جهت همه یال ها رو به جلو باشه ، سوالـه خاصی نیست ولی ممکنه تو سوالا دیگه بدرد بخوره ، الگوریتم ٍ چینشٍش هم جز اینی که معلم ٍتون گفته راحت ترش اینه که به ترتیب دلخواهی روی راس ها dfs بزنی ( مثل موقع چک کردن تعداد مولفه ها همبندی مثلا) بعد dfs ٍ هر راس که تموم شد(ینی آخره آخره تابع) بریزیش توی یه stack ، از سر تا ته ٍ این stack میشه همون ترتیبه.شرط این که چنین ترتیبی ام باشه اینه که گراف دور نداشته باشه .به نقل از daneshvar.a :
به نقل از Alir3za :
for (int i=0;i<n;i++)
if (!mark[i])
{
st.push_back(i);
dfs(i);
}نه دیگعبه نقل از daneshvar.a :
dfs(vert){
for(.....){
...
..
}
st.push(vert);
}
به نقل از Alir3za :نه دیگع
این dfs ٍ؟
این جوریکد:dfs(vert){ for(.....){ ... .. } st.push(vert); }
آره داخل مِین همونجوری dfs بزن ولی این جوری که من نوشتم بریز تو استک .به نقل از daneshvar.a :
#include <bits/stdc++.h>
#define mk make_pair
#define pb push_back
#define L first
#define R second
#define pii pair <int, int>
using namespace std;
const int maxn=1e5+5;
int n, m, mark[maxn], tmp=1, dir;
vector <int> scc, v[2][maxn];
void dfs (int x)
{
mark[x]=tmp;
for (int i=0;i<v[dir][x].size();i++)
if (!mark[v[dir][x][i]]) dfs(v[dir][x][i]);
if (!dir)
scc.pb(x);
}
int main ()
{
cin>>n>>m;
for (int i=0;i<m;i++){
int fi, se;
cin>>fi>>se;
v[0][fi].pb(se);
v[1][se].pb(fi);
}
for (int i=1;i<=n;i++) if (!mark[i]) dfs(i);
memset(mark, 0, sizeof mark), dir=1;
for (int i=1;i<=n;i++) if (!mark[i]) dfs(i), tmp++;
return 0;
}
به نقل از TheBest444 :1_با مجموعه راس های V1 تا V6 چند گراف ساده میتوان رسم کرد که به V1 فرد تا یال وصل باشد؟
2_ 1_با مجموعه راس های V1 تا V6 چند گراف ساده میتوان رسم کرد که به همه ی راس ها ذوج تا یال وصل باشد؟
3_آقای X و خانم Y به نمایندگی کشور انگلستان در جلسه ای شرکت کرده اند. از 3 کشور دیگر نیز 2 نفر در آن جلسه وجود دارند. پس از دست دادن آنها آقای X از همه ی حاظرین درباره ی تعداد دست دادن هایشان میپرسد.با نهایت تعجب همه ی جواب ها متفاوت بود.آقای X با چند نفر دست داده است؟(تعداد دست دادن ها از 0 تا 6 است)
پ.ن: خیلی ممنون میشم اگه جواب بدین
به نقل از علی کوچولو! :فعلا سوال يك، بقيشم برا بعد:
جواب نهايي 16*10^2
توجه كن: انتخاب يك از 5 برا پيدا كردن يه سر يال بعد با5 راس ديگه 10 يال داريم يعد 2 به توان 10 گراف الي اخر...
اولن دقت کنید که دو نفر از یه کشور با هم دست نمیدن!به نقل از TheBest444 :
1- این قسمتی که قرمز کردم درسته؟به نقل از DaneshvarA :
فرض کن کل گرافت یه مسیر به طول 4 باشه، یعنی 4 تا راس و سه تا یال داشته باشه، توی این گراف هر زیرگراف القایی سه راسی تشکیل مسیر میده؟)) دو تا راس که به همدیگه وصل نیستن رو درنظر میگیری بعد اثبات میشه (فک کنم راه تو هم همین بود)به نقل از amoo§majid :1- این قسمتی که قرمز کردم درسته؟
راه حل من باسه این سواله این بود که برهان خلف زدم، با استقرا ثابت کردم اگه حکم برقرار نباشه رئوس اول و آخر هر مسیر از گرافمون به هم وصلن، حالا چون بین هر دو راسی مسیر هست، حتمن گراف کامل میشه که با فرض مسئله تناقض داره. (ولی دیدم بقیه از راهای دیگه هم رفتن، مثلن استقرا روی تعداد رئوس(ولی این راه باگ خورش بالائه
2- آره برهان خلفه، ولی راه تو رو دقیق نفهمیدم چیه
تناقضش که همینهبه نقل از DaneshvarA :
به نقل از amoo§majid :تناقضش که همینه
فرض کن راس 1 و 2 به هم وصل نباشن
درجه ی این دو تا طبق فرض مسئله بزرگتر از صفره
اگر این دو تا راس یه همسایه مشترک داشته باشن و شماره ی اون همسایه هه 3 باشه، الآن یه زیرگراف القایی دو راسی داریم
پس راس 1ام و 2ام هر کدوم حداقل یه همسایه دارن که مشترک نیستن!
فرض کن شماره ی همسایه راس 1ام، 3 باشه و شماره ی همسایه ی راس 2ام 4 باشه
فرض کردیم راس 2 به راس 3 وصل نیست و راس 1 به راس 4 وصل نیست
حالا چی میمونه؟ اگر رئوس 3 و 4 به هم وصل باشن، زیرگراف القایی متشکل از رئوس 1 و 3 و 4 دو یال داره
وگرنه زیر گراف القایی متشکل از رئوس 1 و 2 و 3 و 4 زیرگرافی القایی با دو یال هستش
تناقض!
پس هر دو راسی به همدیگه وصل هستن
+این عکسو هم ببین
به نقل از amoo§majid :1- این قسمتی که قرمز کردم درسته؟
راه حل من باسه این سواله این بود که برهان خلف زدم، با استقرا ثابت کردم اگه حکم برقرار نباشه رئوس اول و آخر هر مسیر از گرافمون به هم وصلن، حالا چون بین هر دو راسی مسیر هست، حتمن گراف کامل میشه که با فرض مسئله تناقض داره. (ولی دیدم بقیه از راهای دیگه هم رفتن، مثلن استقرا روی تعداد رئوس(ولی این راه باگ خورش بالائه
2- آره برهان خلفه، ولی راه تو رو دقیق نفهمیدم چیه
جواب خط اولت رو نمیدونمبه نقل از DaneshvarA :سوال اول، راهی به جز استفرا نداره؟ چون باید بشه یا همون اطلاعات بخش 1 فصل 1 وست بشه این ها رو جواب داد
دقیقا روی چی باید استفرا زد؟ استفرای ضعیف؟ فرض استفرا چیه؟