挑战程序与设计竞赛——算法和数据结构——第12章-图

.@TOC

1. 邻接表 两个一维数组，一个数组存放头节点，另一个彼此存放指针
2. 邻接矩阵 二维数组，行为头节点
   综上：邻接表和邻接矩阵 意思差不多
   

#include
using namespace std;

const int N = 100;


int main()
{
	int M[N][N]; // 0 0 起点的邻接矩阵
	int n, u, k, v;

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> u >> k;
		u--;
		for (int j = 0; j < k; j++)
		{
			cin >> v;
			v--;
			M[u][v] = 1;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (j)cout << " ";
			cout << M[i][j];
		}
		cout << endl;
	}

	return 0;
}

#include
#define N 100
#define WHITE 0  //表示没遍历呢
#define GRAY 1   //表示遍历过，但还得回来
#define BLACK 2	 //表示这个节点的子节点 都遍历完了

int n, M[N][N];
int color[N], d[N], f[N], tt;
	
// 用递归函数实现的深度优先搜索
// 这个是真正的深搜递归

void dfs_visit(int u)
{
	int v;
	color[u] = GRAY;
	d[u] = ++tt;
	for (v = 0; v < n; v++)
	{
		if (M[u][v] == 0)continue;
		if (color[v] == WHITE)
			dfs_visit(v);//直接遍历这个节点
	}
	color[u] = BLACK;
	f[u] = ++tt;
}

void dfs() {
	int u;
	for (u = 0; u < n; u++)
		color[u] = WHITE;
	tt = 0;
	// 这个遍历，是保证所有节点，都走到。防止出现未联通的节点
	for (u = 0; u < n; u++)
	{
		if (color[u] == WHITE)
			dfs_visit(u);
	}
	for (u = 0; u < n; u++)
	{
		printf("%d %d %dn", u + 1, d[u], f[u]);
	}
}

int main()
{
	int u, v, k, i, j;

	scanf("%d", &n);

	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
			M[i][j] = 0;
	}

	for (i = 0; i < n; i++)
	{
		scanf("%d %d", &u, &k);
		u--;
		for (j = 0; j < k; j++)
		{
			scanf("%d", &v);
			v--;
			M[u][v] = 1;
		}
	}
	dfs();
	return 0;
}

#include
#include
using namespace std;

const int N = 100;
const int WHITE = 0;
const int GRAY = 1;
const int BLACK = 2;

int n, M[N][N];
int color[N], d[N], f[N], tt;
int nt[N];

//得到 u 节点 连着的节点
int next(int u)
{
	for (int v = nt[u]; v < n; v++)
	{
		//nt【u】 的值 用来记录 u这个点，遍历到了哪个点，接下来该根据这个值，继续遍历
		nt[u] = v + 1; 
		if (M[u][v])return v;
	}
	return -1;
}


void dfs_visit(int r)
{
	for (int i = 0; i < n; i++)
		nt[i] = 0;

	stack S;
	S.push(r);
	color[r] = GRAY;
	//入队列的同时，记录当前是tt多少，进入的
	d[r] = ++tt;

	while (!S.empty())
	{
		// u 这个可能会多次回溯到，因为是深度搜索
		int u = S.top();
		int v = next(u);

		if (v != -1)
		{
			if (color[v] == WHITE)
			{
				color[v] = GRAY;
				d[v] = ++tt;
				S.push(v);
			}
		}
		else
		{
			S.pop();
			color[u] = BLACK;
			f[u] = ++tt;	
		}
	}
}

void dfs()
{
	for (int i = 0; i < n; i++)
	{
		color[i] = WHITE;
		nt[i] = 0;
	}
	tt = 0;

	for (int u = 0; u < n; u++)
	{
		if (color[u] == WHITE)
			dfs_visit(u);
	}
}

int main()
{
	int u, k, v;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
			M[i][j] = 0;
	}

	for (int i = 0; i < n; i++)
	{
		cin >> u >> k;
		u--;
		for (int j = 0; j < k; j++)
		{
			cin >> v;
			v--;
			M[u][v] = 1;
		}
	}

	dfs();

	return 0;

}

#include
#include

using namespace std;
const int N = 100;
const int INFTY = (1 << 21);

int n, M[N][N];
int d[N];

void bfs(int s)
{
	queue q;
	q.push(s);
	for (int i = 0; i < n; i++)
	{
		d[i] = INFTY;
	}
	d[s] = 0;
	int u;
	while (!q.empty())
	{
		u = q.front();
		q.pop();
		for (int v = 0; v < n; v++)
		{
			if (M[u][v] == 0)
				continue;
			if (d[v] != INFTY)
				continue;

			d[v] = d[u] + 1;
			q.push(v);
		}
	}
	for (int i = 0; i < n; i++)
	{
		cout << i + 1 << " " << ((d[i] == INFTY) ? (-1) : d[i]) << endl;
	}

}


int main()
{
	int u, k, v;
	
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			M[i][j] = 0;
		}
	}

	for (int i = 0; i < n; i++)
	{
		cin >> u >> k;
		u--;
		for (int j = 0; j < k; j++)
		{
			cin >> v;
			v--;
			M[u][v] = 1;
		}
	}

	bfs(0);

	return 0;

}

#include
#include
#include

using namespace std;
const int MAX = 10000;
const int NIL = -1;

int n;

//vector邻接表（不仅是数组，而且可以pop等操作，无需角标）
vector G[MAX];

int color[MAX];

//带“颜色”的深搜
void dfs(int r, int c)
{
	stack S;
	S.push(r);
	color[r] = c;
	while (!S.empty())
	{
		int u = S.top();
		S.pop();
		for (int i = 0; i < G[u].size(); i++)
		{
			int v = G[u][i];
			if (color[v] == NIL)
			{
				color[v] = c;
				S.push(v);
			}
		}
	}
}

void assignColor()
{
	int id = 1;
	for (int i = 0; i < n; i++)
		color[i] = NIL;
	//对每个节点 进行深搜 并且在 深搜的同时 把点上色（色就是1 2 3即可）
	for (int u = 0; u < n; u++)
	{
		if (color[u] == NIL)
			dfs(u, id++);
	}
}

int main()
{
	int s, t, m, q;

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> s >> t;
		G[s].push_back(t);
		G[t].push_back(s);
	}

	assignColor();

	cin >> q;

	for (int i = 0; i < q; i++)
	{
		cin >> s >> t;
		if (color[s] == color[t])
		{
			cout << "yes" << endl;
		}
		else
		{
			cout << "no" << endl;
		}
	}

}