POJ 2186 解题报告

本文主要是介绍POJ 2186 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题是求最强连通分量，将图压缩，即属于一个强连通分量的所有点变成一个点，然后看出度为0的点有多少个。因为最popular的牛不应该有出去的边，反之亦成立。如果我们只有一个点（压缩点）没有出度，那么输出这个压缩点所代表的所有点，即属于这个强连通分量的所有点。这些牛是等效的。否则，多于一个点没有出度，这时图是不连通的，输出0。不可能没有出度为0的点(a little hard to explain)。

需要说的是out[usccno]++;对出度的计算是不准确的（因为一个强连通分量到另一个强连通分量的连接可能被计算多次），但是由于我们只判断出度是否为0，所以这里是足够的。我曾经改成vector<bool>，结果时间显著增大了。不知道为什么。

thestoryofsnow

2186

Accepted

1548K

297MS

C++

3290B

/* 
ID: thestor1 
LANG: C++ 
TASK: poj2186 
*/
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <limits>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <cassert>using namespace std;bool isundefined(int u, std::vector<int> &indexes)
{return indexes[u] < 0;
}void strongconnect(int u, int &index, std::vector<int> &indexes, std::vector<int> &lowlinks, int &SCCNO, std::vector<int> &sccnos, stack<int> &S, std::vector<bool> &onStack, const std::vector<std::vector<int> > &adjs)
{// Set the depth index for u to the smallest unused indexindexes[u] = index;lowlinks[u] = index;index++;S.push(u);onStack[u] = true;// Consider successors of ufor (int i = 0; i < adjs[u].size(); ++i){int v = adjs[u][i];if (isundefined(v, indexes)){// Successor v has not yet been visited; recurse on itstrongconnect(v, index, indexes, lowlinks, SCCNO, sccnos, S, onStack, adjs);lowlinks[u] = min(lowlinks[u], lowlinks[v]);}else if (onStack[v]){// Successor v is in stack S and hence in the current SCClowlinks[u] = min(lowlinks[u], lowlinks[v]);	}}// If u is a root node, pop the stack and generate an SCCif (indexes[u] == lowlinks[u]){// start a new strongly connected componentwhile (true){int v = S.top();S.pop();onStack[v] = false;// add v to current strongly connected componentsccnos[v] = SCCNO;if (v == u){break;}}SCCNO++;}
}// Tarjan's strongly connected components algorithm
// See http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
void tarjan(const int N, const std::vector<std::vector<int> > &adjs, int &SCCNO, std::vector<int> &sccnos)
{int index = 0;std::vector<int> indexes(N, -1);std::vector<int> lowlinks(N, -1);stack<int> S;std::vector<bool> onStack(N, false);for (int u = 0; u < N; ++u){if (isundefined(u, indexes)){strongconnect(u, index, indexes, lowlinks, SCCNO, sccnos, S, onStack, adjs);}}}int main()
{int N, M;scanf("%d%d", &N, &M);std::vector<std::vector<int> > adjs(N, std::vector<int>());for (int i = 0; i < M; ++i){int A, B;scanf("%d%d", &A, &B);A--, B--;adjs[A].push_back(B);}int SCCNO = 0;std::vector<int> sccnos(N, -1);tarjan(N, adjs, SCCNO, sccnos);// printf("SCCNO: %d\n", SCCNO);// for (int i = 0; i < N; ++i)// {// 	printf("%d:%d\n", i, sccnos[i]);// }std::vector<int> size(SCCNO, 0), out(SCCNO, 0);for (int u = 0; u < N; ++u){int usccno = sccnos[u];size[usccno]++;for (int i = 0; i < adjs[u].size(); ++i){int vsccno = sccnos[adjs[u][i]];if (usccno != vsccno){out[usccno]++;}}}int zeroout = 0, zerooutscc = -1;for (int i = 0; i < SCCNO; ++i){if (out[i] == 0){zeroout++;zerooutscc = i;}}if (zeroout > 1){printf("0\n");}else if (zeroout == 1){printf("%d\n", size[zerooutscc]);}else{assert(false);}return 0;  
}

这篇关于POJ 2186 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---