Rezultati

Up. imeNalogaJezikRezultatČas oddaje
EOF-2017 Trgovec C++ 100/100OK 11. maj '17 @ 19:12

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 7,656 MiB 0,010 s OK
#2 3/3 7,656 MiB 0,010 s OK
#3 3/3 7,559 MiB 0,010 s OK
#4 3/3 7,656 MiB 0,016 s OK
#5 3/3 7,559 MiB 0,016 s OK
#6 3/3 7,559 MiB 0,016 s OK
#7 3/3 7,656 MiB 0,016 s OK
#8 3/3 7,559 MiB 0,016 s OK
#9 3/3 7,559 MiB 0,016 s OK
#10 3/3 7,656 MiB 0,016 s OK
#11 3/3 7,660 MiB 0,016 s OK
#12 3/3 7,664 MiB 0,016 s OK
#13 3/3 7,660 MiB 0,016 s OK
#14 3/3 7,559 MiB 0,010 s OK
#15 3/3 7,660 MiB 0,016 s OK
#16 3/3 7,676 MiB 0,010 s OK
#17 3/3 7,676 MiB 0,010 s OK
#18 3/3 7,672 MiB 0,010 s OK
#19 3/3 7,578 MiB 0,016 s OK
#20 3/3 7,977 MiB 0,028 s OK
#21 4/4 19,156 MiB 0,323 s OK
#22 4/4 16,375 MiB 0,330 s OK
#23 4/4 16,281 MiB 0,342 s OK
#24 4/4 13,367 MiB 0,264 s OK
#25 4/4 12,148 MiB 0,245 s OK
#26 4/4 16,508 MiB 0,312 s OK
#27 4/4 16,133 MiB 0,299 s OK
#28 4/4 13,461 MiB 0,270 s OK
#29 4/4 12,164 MiB 0,233 s OK
#30 4/4 11,566 MiB 0,228 s OK

Ocenjevani program (Trgovec (2).cpp):
/*
Tarjan's Algorithm for Strongly Connected Components (Directed Graph)
O(E + V)
*/

#include <iostream>
#include <list>
#include <stack>
#include <algorithm>
#define SIZE 100003
using namespace std;


stack<int> stk;
list<pair<int, int> > adj_ssc[SIZE]; //Adjacency List
list<int> GRAF[SIZE];
int DFS_visitedSSC[SIZE];
int DFS_minSSC[SIZE];
bool inStk[SIZE];
int component[SIZE];
int cnter;
int stcomponent;
bool konec;
int n;

void DFS_visitA(int index) {
	DFS_visitedSSC[index] = cnter++;
	DFS_minSSC[index] = DFS_visitedSSC[index];
	stk.push(index);
	inStk[index] = true;

	for (list<pair<int, int> >::iterator it = adj_ssc[index].begin(); it != adj_ssc[index].end(); it++) {
		if (DFS_visitedSSC[it->first] == -1) {
			DFS_visitA(it->first);
			DFS_minSSC[index] = min(DFS_minSSC[index], DFS_minSSC[it->first]);
		}
		else if (inStk[it->first]) {
			DFS_minSSC[index] = min(DFS_minSSC[index], DFS_visitedSSC[it->first]);
		}
	}

	if (DFS_visitedSSC[index] == DFS_minSSC[index]) {
		//cout << "Strongly connected component: ";
		int i;
		do {
			i = stk.top();
			stk.pop();
			inStk[i] = false;
			//cout << i << " ";
			component[i] = stcomponent;
		} while (i != index);
		stcomponent++;
		//cout << endl;
	}
	return;
}

void Make_Graph(int v) {
	DFS_visitedSSC[v] = 1;
	
	for (list<pair<int, int> >::iterator it = adj_ssc[v].begin(); it != adj_ssc[v].end(); ++it) {
		if (component[v] != component[it->first]) {
			GRAF[component[v]].push_back(component[it->first]);
		}
		if (DFS_visitedSSC[it->first] == -1) Make_Graph(it->first);
	}
	return;
}

void Preglej(int v) {
	inStk[v] = true;
	for (list<int>::iterator it = GRAF[v].begin(); it != GRAF[v].end(); ++it) {
		Preglej(*it);
		if (konec == true)return;
	}
	if (GRAF[v].size() == 0) {
		int i;
		for (i = 0; i < stcomponent; i++) {
			if (inStk[i] == false) break;
		}
		if (i == stcomponent) {
			konec = true;
			return;
		}
	}
	inStk[v] = false;
	return;
}

int main() {
	//Sample input
	konec = false;
	cnter = stcomponent = 0;
	int m, x, y, w = 0, z;
	cin >> n >> m >> z;

	for (int i = 0; i < m; i++) {
		cin >> x >> y/*>>w*/;
		adj_ssc[x].push_back(make_pair(y, w));
	}

	//DFS init

	for (int i = 0; i <= n; i++) {
		DFS_visitedSSC[i] = -1;
		DFS_minSSC[i] = -1;
		inStk[i] = false;
	}
	for (int i = 1; i <= n; i++) {
		if (DFS_visitedSSC[i] == -1) {
			DFS_visitA(i);
		}
	}
	fill(DFS_visitedSSC, DFS_visitedSSC + n + 1, -1);
	for (int i = 1; i <= n; i++) {
		if (DFS_visitedSSC[i] == -1) {
			Make_Graph(i);
		}
	}
	fill(inStk, inStk + n + 1, false);
	/*
	for (int i = 0; i < stcomponent; i++) {
		cout << i << ' ';
		for (list<int>::iterator it = GRAF[i].begin(); it != GRAF[i].end(); ++it) {
			cout << *it << ' ';
		}
		cout << endl;
	}
	*/

	Preglej(component[z]);

	if (konec == true) cout << "DA";
	else cout << "NE";

	return 0;
}