学步园

很久就说要总结强连通的题目就是不总结，这不你爽了吧！

今天的那个题目，明显就应该是强连通方面的题目，自己愣是看着也无从下手，无力呀。

说好的好好学几天，最后几天了，可是还是静不下心来，你这让我怎么说？

贴出这个无向图求强连通分量的代码吧：

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <string>

using namespace std;

const int MAXN = 100 + 11;

int N, M, vis[MAXN], current_cc, cc[MAXN];

vector <int> G[MAXN];

void addEdge(int from, int to)
{
	G[from].push_back(to);
}

void DFS(int u)
{
	vis[u] = 1;
	cc[u] = current_cc;
	int nc = G[u].size();
	for (int i = 0; i < nc; i++)
	{
		int v = G[u][i];
		if (!vis[v])
		{
			DFS(v);
		}
	}
}

int find_cc()
{
	current_cc = 0;
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= N; i++)
	{
		if (!vis[i])
		{
			current_cc++;
			DFS(i);
		}
	}
	return current_cc;
}

void print()
{
	printf("print the cc:\n");
	for (int i = 1; i <= N; i++)
	{
		printf("cc[%d] = %d\n", i, cc[i]);
	}
}

void init()
{
	for (int i = 0; i < N; i++)
	{
		G[i].clear();
	}
//	edges.clear();
}

int main()
{
	int a, b;
	while (scanf("%d%d", &N, &M) != EOF)
	{
		init();
		for (int i = 0; i < M; i++)
		{
			scanf("%d%d", &a, &b);
			addEdge(a, b);
			addEdge(b, a);
		}
		int ans = find_cc();
		printf("the connected component is %d\n", ans);
		print();
	}
	return 0;
}