Rezultati

Up. imeNalogaJezikRezultatČas oddaje
rektifikatorji-2018 Dolenjec C++ 100/100OK 10. maj '18 @ 19:59

Test Točke Porabljen spomin Porabljen čas Status
#1 3/3 2,984 MiB 0,000 s OK
#2 3/3 3,035 MiB 0,004 s OK
#3 3/3 2,988 MiB 0,000 s OK
#4 3/3 3,043 MiB 0,004 s OK
#5 3/3 2,984 MiB 0,004 s OK
#6 3/3 3,043 MiB 0,004 s OK
#7 3/3 3,039 MiB 0,004 s OK
#8 3/3 3,043 MiB 0,004 s OK
#9 3/3 2,980 MiB 0,000 s OK
#10 3/3 3,043 MiB 0,004 s OK
#11 3/3 3,043 MiB 0,004 s OK
#12 3/3 2,988 MiB 0,004 s OK
#13 3/3 2,992 MiB 0,004 s OK
#14 3/3 3,043 MiB 0,004 s OK
#15 3/3 3,043 MiB 0,004 s OK
#16 3/3 3,047 MiB 0,004 s OK
#17 3/3 3,043 MiB 0,000 s OK
#18 3/3 3,070 MiB 0,004 s OK
#19 3/3 3,070 MiB 0,004 s OK
#20 3/3 3,016 MiB 0,004 s OK
#21 3/3 3,020 MiB 0,004 s OK
#22 3/3 3,371 MiB 0,016 s OK
#23 3/3 16,875 MiB 0,262 s OK
#24 3/3 12,059 MiB 0,255 s OK
#25 3/3 13,480 MiB 0,225 s OK
#26 3/3 10,426 MiB 0,202 s OK
#27 3/3 8,914 MiB 0,233 s OK
#28 3/3 11,527 MiB 0,244 s OK
#29 3/3 13,234 MiB 0,256 s OK
#30 3/3 10,633 MiB 0,202 s OK
#31 3/3 8,855 MiB 0,190 s OK
#32 3/3 7,742 MiB 0,197 s OK
#33 4/4 2,984 MiB 0,004 s OK

Ocenjevani program (Source (3).cpp):
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <stack>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#define NIL -1
using namespace std;

bool* cycled;

//Tarjanov algoritem

class Graph {
	void SCCUtil(int u, int disc[], int low[],
		stack<int> *st, bool stackMember[]);
public:
	Graph(int V);
	void addEdge(int v, int w);
	void SCC();
	list<int> *adj;
	int V;
};

Graph::Graph(int V) {
	this->V = V;
	adj = new list<int>[V];
}

void Graph::addEdge(int v, int w) {
	adj[v].push_back(w);
}

void Graph::SCCUtil(int u, int disc[], int low[], stack<int> *st,
	bool stackMember[]) {
	static int time = 0;

	disc[u] = low[u] = ++time;
	st->push(u);
	stackMember[u] = true;

	list<int>::iterator i;
	for (i = adj[u].begin(); i != adj[u].end(); ++i) {
		int v = *i;

		if (disc[v] == -1) {
			SCCUtil(v, disc, low, st, stackMember);

			low[u] = min(low[u], low[v]);
		}

		else if (stackMember[v] == true)
			low[u] = min(low[u], disc[v]);
	}

	int w = 0;
	int sz = st->size();
	if (low[u] == disc[u]) {
		while (st->top() != u) {
			w = (int)st->top();
			cycled[w] = true;
			cycled[u] = true;
			stackMember[w] = false;
			st->pop();
		}
		w = (int)st->top();
		stackMember[w] = false;
		st->pop();
	}
}

void Graph::SCC() {
	int *disc = new int[V];
	int *low = new int[V];
	bool *stackMember = new bool[V];
	stack<int> *st = new stack<int>();

	for (int i = 0; i < V; i++) {
		disc[i] = NIL;
		low[i] = NIL;
		stackMember[i] = false;
	}

	for (int i = 0; i < V; i++)
	if (disc[i] == NIL)
		SCCUtil(i, disc, low, st, stackMember);
}

int main() {
	int n, m, d, start;
	cin >> n >> m >> d >> start;
	bool* gostilne = new bool[n];
	cycled = new bool[n];
	bool* visited = new bool[n];
	memset(visited, false, n * sizeof(bool));
	memset(cycled, false, n * sizeof(bool));
	memset(gostilne, false, n * sizeof(bool));
	int t;
	for (int i = 0; i < d; ++i) {
		cin >> t;
		gostilne[t - 1] = true;
	}

	int tt;
	Graph g(n);
	for (int i = 0; i < m; ++i) {
		cin >> t >> tt;
		g.addEdge(t - 1, tt - 1);
	}
	g.SCC();

	int currentPosition;
	stack<int> st;
	st.push(start - 1);
	while (!st.empty()) {//DFS
		currentPosition = st.top();
		st.pop();
		for (auto i = g.adj[currentPosition].begin(); i != g.adj[currentPosition].end(); ++i) {
			if (gostilne[*i]) {
				if (cycled[*i]) {
					cout << "DA\n";
					//system("pause");
					return 0;
				} else if (*i == currentPosition) {
					cout << "DA\n";
					//system("pause");
					return 0;
				}
			}
			if (!visited[*i]) {
				visited[*i] = true;
				st.push(*i);
			}
		}
	}
	cout << "NE\n";

	//system("pause");
	return 0;
}