dfs-bfs-adjlist.cpp 1.23 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
#include <cstdio>
#include <cstring>
#include <vector>

#define MAXN 15
#define pb push_back

using namespace std;

vector<int> e[MAXN];
int vis[MAXN], N, M;

void Read() {
	int i, a, b;

	scanf ("%d %d", &N, &M);
	for ( i=1; i<=M; ++i ) {
		scanf ("%d %d", &a, &b);
		e[a].pb ( b );
	}
}

bool Cycle ( int v ) {
	int i, neib;

	vis[v] = 1; // 1 means under process
	for ( i=0; i<e[v].size(); ++i ) {
		neib = e[v][i];
		if ( vis[ neib ] == 1 ) {
			return true;
		}
		else if ( vis[ neib ] == 0 ) {
			if ( Cycle( neib ) ) {
				return true;
			}
		}
	}

	vis[v] = 2; // finished it
	return false;
}

void Bfs ( int source ) {
	int i, j, v, neib, queue[MAXN], nqueue = 0;

	memset ( vis, 0, sizeof(vis) );

	queue[ nqueue++ ] = source;
	vis[source] = 1;

	for ( i=0; i<nqueue; ++i ) {
		v = queue[i];
		printf ("%d reachable from %d\n", v, source );
		for ( j=0; j<e[v].size(); ++j ) {
			neib = e[v][j];
			if ( !vis[ neib ] ) {
				queue[ nqueue++ ] = neib;
				vis[neib] = 1;
			}
		}
	}
}

int main ( void ) {
	int i;

	Read();
	//Detect cycle with DFS
	memset ( vis, 0, sizeof(vis) );
	for ( i=1; i<=N; ++i ) {
		if ( !vis[i] ) {
			if ( Cycle(i) ) {
				printf ("Found cycle\n");
			}
		}
	}
	//Report all nodes reachable from node 2, with BFS
	Bfs(2);
}