题目：http://acm.hdu.edu.cn/showproblem.php?pid=1827
第二道强连通分量题目， 对于SCC也有了一定的认识， 所以想在这里总结一下；有向非强连通图的极大强连通子图叫做强连通分量 (SCC), 所有强连通分量在原图中组成一个DAG(每个强连通分量看作一个点)。TarJan() 算法利用Dfs找强连通分量， 我们可以把Dfs搜索过程看作是一个整体，个人感觉分步模拟并不是很好理解。
Low[]: 时间戳；（树根）。
dfn[]; 记录搜索当前节点的时间。
当搜索到强连通分量时， 让根节点及其以上节点弹出栈。（instack[u] = 0）。可以进行操作是记录SCC个数 && 缩点 && 记录SCC中结点的个数。
本题题意是在一个有向关系图中， 花最少的话费， 把消息通知到所有人。
看SCC入度 V， V！= 0 不需花费， V == 0， 取花费最少节点， 注意操作一致性。
#include#include #include #include using namespace std;const int INF = 0x3f3f3f3f;int dfn[1001], low[1001], instack[1001], sccf[1001], Rdu[1001], Cost[1001], cnt_SCC, vis_num, total, n, m;struct Edge{ int from, to, next;} edge[2010];int cnt, head[1001];void Add(int a, int b){ Edge E = {a, b, head[a]}; edge[cnt] = E; head[a] = cnt++;}stack S;void TarJan(int x){ int j; dfn[x] = low[x] = ++vis_num; instack[x] = 1; S.push(x); for(int i = head[x]; i != -1; i = edge[i].next) { int u = edge[i].to; if(dfn[u] == -1) { TarJan(u); if(low[x] > low[u]) low[x] = low[u]; } else if(instack[u] && low[x] > dfn[u]) low[x] = dfn[u]; } if(low[x] == dfn[x]) { cnt_SCC++; do{ j = S.top(); sccf[j] = cnt_SCC; S.pop(); instack[j] = 0; } while(j != x); }}void Deal() //确定结果； { for(int i = 1; i <= n; i++) { for(int k = head[i]; k != -1; k = edge[k].next) { int u = edge[k].to; if(sccf[u] != sccf[i]) Rdu[sccf[u]]++; } } int ReSult = 0; for(int i = 1; i <= cnt_SCC; i++) { if(!Rdu[i]) { ReSult++; int minn = INF; for(int j = 1; j <= n; j++) { if(sccf[j] == i) minn = min(minn, Cost[j]); } total += minn; } } printf("%d %d\n", ReSult, total);}void SolVe(){ vis_num = cnt_SCC = total = 0; for(int i = 1; i <= n; i++) if(dfn[i] == -1) TarJan(i);// printf("%d\n", cnt_SCC);} void GetMap(){ memset(Rdu, 0, sizeof(Rdu)); memset(low, 0, sizeof(low)); memset(dfn, -1, sizeof(dfn)); memset(head, -1, sizeof(head)); memset(instack, 0, sizeof(instack)); cnt = 0; for(int i = 1; i <= m; i++) { int a, b; scanf("%d %d", &a, &b); Add(a, b); }}int main(){ while(~scanf("%d %d", &n, &m)) { for(int i = 1; i <= n; i++) scanf("%d", &Cost[i]); GetMap(); SolVe(); Deal(); } return 0;}