მეტრო



მეტროს სქემა, რომელიც დამახასიათებელია ბერლანდის ყველა ქალაქისთვის, წარმოდგენილია n სადგურის სახით, რომლებიც n გადასასვლელითაა დაკავშირებული ერთმანეთთან. თითოეული გადასასვლელი აკავშირებს ზუსტად ორ სადგურს, ისე რომ არ კვეთს სხვას. გარდა ამისა, ამ სქემაში მგზავრს შეუძლია მოხვდეს ნებისმიერიდან ნებისმიერ სადგურზე გადასასვლელების გავლით. ისინი ორმხრივია და ორ სადგურს შორის მათი რაოდენობა ერთს არ აღემატება.

ბერლანდის მათემატიკოსებმა დაამტკიცეს თეორია რომლის მიხედვითაც ყველა მსგავს მეტროს სქემას აქვს ე.წ წრიული გზა(ringroad) და თანაც მხოლოდ ერთი.  სხვა სიტყვებით რომ ვთქვათ სქემის გრაფი შეიცავს ციკლს.

ამ მიგნებას დიდი სოციალური გავლენა ქონდა, იმის გამო რომ მოსახლეობას ახლა უკვე შეეძლო სადგურები ერთმანეთთან შეედარებინა ციკლიდან დაშორებული მანძილით. მაგალითად, თუკი ერთი მოქალაქე იტყოდა: “მე წრიდან 3 გადასასვლელით შორს ვცხოვრობ”, მეორეს უპასუხებდა: “ლუზერო, ჩემი სახლი წრიდან მხოლოდ 1 გადასასვლელითაა დაშორებული”. ინტერნეტიც სულ მალე მოიცვა აპლიკაციებმა რომლებიც პირდებოდა ხალხს რომ დაითვლიდა დაშორებას ციკლური გზიდან კონკრეტულ სადგურამდე.

ბერლანდის მთავრობამ გადაწყვიტა ბოლო მოეღო გაუგებრობებისთვის და სიტუაცია გაეკონტროლებინა. თქვენ გევალებათ დაწეროთ პროგრამა რომელიც დაადგენს დაშორებას ციკლიდან ნებისმიერი სადგურისთვის.


შემომავალი ინფორმაცია
პირველი ხაზი შეიცავს მთელ რიცხვ n-ს (3 ≤ n ≤ 3000), რომელიც არის სადგურების რაოდენობა მეტროს სქემაში. მომდევნო n ხაზი აღწერს გადასასვლელებს. თითოეული მათგანი შეიცავს ორ მთელ რიცხვს  xi, yi (1 ≤ xi, yi ≤ n) რაც ნიშნავს რომ xi-დან yi-მდე არის პირდაპირი გზა. სადგურები გადანომრილია 1-დან n-მდე. გარანტირებულია რომ  xi ≠ yi, ორ სადგურს შორის არსებობს მხოლოდ ერთი პირდაპირი გადასასვლელი და მისი გამოყენება შესაძლებელია ორივე მხრიდან.

გამოსატანი ინფორმაცია
დაბეჭდეთ n ცალი რიცხვი. გამოყავით რიცხვები ერთმანეთისგან სფეისით. i-ური რიცხვი უნდა იყოს i-ური სადგურის ციკლიდან დაშორების სიგრძის ტოლი. თავად ციკლის სადგურებისთვის დაბეჭდეთ 0.


 მაგალითები:
 შემომავალი:
 4
 1 3
 4 3
 4 2
 1 2

 გამოსატანი:
 0 0 0 0


 შემომავალი:
 6
 1 2
 3 4
 6 4
 2 3
 1 3
 3 5

 გამოსატანი:
 0 0 0 1 1 2


 

პირველ რიგში მეტროს სქემა წარმოვიდგინოთ გრაფის სახით. პირობის მიხედვით ნებისმიერი სადგურიდან ნებისმიერში მივალთ, რაც ნიშნავს რომ გრაფი ბმულია.

გრაფთა თეორიიდან ვიცით რომ თუკი გრაფი ბმულია და მასში წვეროებისა და წიბოების რაოდენობა ტოლია იგი შეიცავს ზუსტად ერთ ციკლს. ჩვენი ამოცანაც სწორედ ამ ციკლის პოვნა და ყველა წვეროსთვის აქედან მანძილის გამოთვლაა.

(ციკლის წვეროებისთვის ეს მანძილი იქნება 0, მათი მეზობლებისთვის - 1, იმათი მეზობლებისთვის - 2 და ა.შ.)

ლოგიკური იქნება თუ ჯერ ციკლს ანუ იმ წვეროების ერთობლიობას ვიპოვით რომელთათვისაც პასუხი 0-ია. ციკლის პოვნა მარტივად არის შესაძლებელი სიღრმეში ძებნის ალგორითმით. გზადაგზა თითოეული წვეროსთვის მშობელს(საიდანაც მიმდინარე წვეროში გადმოვედით) დავიმახსოვრებთ და როგორც კი ციკლი “შეიკვრება” საწყის და საბოლოო წვეროებს დავაფიქსირებთ. ბოლოს დამახსოვრებული მშობლების საშუალებით ბოლოდან გამოვუყვებით და ციკლის ყველა წვეროს მივიღებთ.

ამის შემდეგ დაგვჭირდება ციკლის წვეროებიდან სათითაოდ გავუშვათ ძებნის ალგორითმი რომელიც გადაუყვება მეზობლებს და მათთვის გამოითვლის ციკლიდან დაშორებას(ყოველი შემდეგი წვეროსთვის ეს რიცხვი იქნება მშობელის დაშორებას დამატებული ერთი).

საბოლოოდ, ყველა ძებნა ჯამში სულ ორჯერ მოივლის მთელ გრაფს რაც გვაძლევს O(N) სირთულის ამოხსნას.

 

ამოხსნა:

#include <iostream>
using namespace std;

int n, x, y, cyclestart, cycleend, res[3001], parent[3001], visited[3001], graph[3001][3001], cycle[3001];

bool detectCycle(int cur, int par){
	if(visited[cur]){
		cyclestart = cur;
		cycleend = par;
		return true;
	}else{
		visited[cur] = 1;
		parent[cur] = par;
	}

	for(int i = 1; i <= graph[cur][0]; i++){
		if(graph[cur][i] != par){
			if(detectCycle(graph[cur][i], cur)){
				return true;
			}
		}
	}

	return false;
}

void markDistances(int cur, int dist){
	visited[cur] = 1;
	res[cur] = dist;

	for(int i = 1; i <= graph[cur][0]; i++){
		if(!visited[graph[cur][i]]){
			markDistances(graph[cur][i], dist + 1);
		}
	}
}

int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> x >> y;
		graph[x][++graph[x][0]] = y;
		graph[y][++graph[y][0]] = x;
	}

	if(detectCycle(1, 1)){
		for(int i = 1; i <= n; i++){
			visited[i] = 0;
		}

		cycle[++cycle[0]] = cycleend;
		visited[cycleend] = 1;
		res[cycleend] = 0;

		while(cycleend != cyclestart){
			cycleend = parent[cycleend];

			cycle[++cycle[0]] = cycleend;
			visited[cycleend] = 1;
			res[cycleend] = 0;
		}

		for(int i = 1; i <= cycle[0]; i++){
			markDistances(cycle[i], 0);
		}

		for(int i = 1; i <= n; i++){
			cout << res[i] << " ";
		}
		cout << endl;
	}else{
		cout << -1 << endl;
	}

	return 0;
}