[URI ONLINE JUDGE] – 1610 – Dudu Service Maker

Dudu needs a document to finalize a task in his work. After searching, he found out that this document needed other documents, which also needed other documents and so on.

Dudu made a final list with the documents he will need. With that in hands, he suspects that the list contains loops. For instance, if a document A depends on the document B that also depends on A, it would make the task impossible to finish. In this case the loop contains only two documents, but there might be cases with three or more!

Given the list of the dependencies, help him compute if he can obtain all the documents, it is, to compute if there isn’t a loop in the given dependencies.

Input

The first line contains an integer T (T = 100) indicating the number of test cases.

On the first line in each test case there will be the integers N (2 ≤ N ≤ 100* or 2 ≤ N ≤ 104**) and M (1 ≤ M ≤ 300* or 1 ≤ M ≤ 3*104​**), indicating the number of documents and the dependencies. In each of the following M lines, there will be two integers A (1 ≤ A) and B (BN and A != B) , indicating that the document A depends on the document B. There might be repeated dependencies!

*For around 90% of the cases;

**For the other cases.

Output

For each case, print SIM (Portuguese word for YES) if there is at least one loop, and NAO otherwise (Portuguese word for NO).

Sample Input Sample Output
3

2 1

1 2

2 2

1 2

2 1

4 4

2 3

3 4

4 2

1 3

NAO

SIM

SIM

my solution:

<br />#include <iostream>
#include <stdlib.h>
#include <list>
#include <vector>
#include <sstream>
#include <string>

using namespace std;

const int NOT_VISITED = 0;
const int VISITED = 1;
const int FINISHED = 2;

typedef struct graph {
vector<int> status;
vector< vector<int> > adjacentsTable; // Composed by only adjacents. Not a nxn table.

// Methods
void Graph(int quantity) {
// +1 is just to make the rest of the process easy to read.
status = vector<int>(quantity+1);
adjacentsTable = vector< vector<int> > (quantity+1 , vector<int>());
}

void addAdjacent(int vertex, int adjacent) {
adjacentsTable[vertex].push_back(adjacent);
}

bool depthFirstBreadth(int vertex) {
status[vertex] = VISITED;

// cout << "Vertex: " << vertex << endl;
// cout << "Adjacents Size: " << adjacentsTable[vertex].size() << endl;

for(int index=0; index<adjacentsTable[vertex].size(); index++) {
int adjacentVertex = adjacentsTable[vertex][index];

// cout << "Adjacents Vertex: " << adjacentsTable[vertex][index] << endl;
// cout << "Adjacents Vertex Status: " << status[adjacentVertex] << endl << endl;

if(status[adjacentVertex] == NOT_VISITED) {
if(!depthFirstBreadth(adjacentVertex)) {
return false;
}
} else if(status[adjacentVertex] == VISITED) {
return false;
}
}

status[vertex] = FINISHED;
return true;
}

void searchCycles() {
for(int index = 1; index < status.size(); index++) {
// cout << "DFS ON: " << index << endl << endl;
if(!depthFirstBreadth(index)) {
cout << "SIM" << endl;
return;
}
}

cout << "NAO" << endl;
}


} Graph;

// From C++ Documentation
int stringToInt (string input) {
int number = 0;

stringstream myStream(input);

if (myStream >> number) {
return number;
} else {
return -1;
}
};

int main () {
int testsQuantity, dependencies, verticesQuantity, vertex, adjacent;
string input = "";

cin >> input;

testsQuantity = stringToInt(input);

for(int index = 0; index < testsQuantity; index++) {
Graph graph;

cin >> input;
verticesQuantity = stringToInt(input);

cin >> input;
dependencies = stringToInt(input);

graph.Graph(verticesQuantity);

for(int indexDependencies = 0; indexDependencies < dependencies; indexDependencies++) {
cin >> input;
vertex = stringToInt(input);

cin >> input;
adjacent = stringToInt(input);

graph.addAdjacent(vertex, adjacent);
}

// Resolve hear
graph.searchCycles();

}
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s