题意:告诉你顶点数和边数并输入边的信息,按从小到大输出出度为0的点。其实这道题英文我没看懂,看的图论书才懂的。
就是tarjan缩点,最后输出缩点后所有出度为0的点,和POJ2186的代码一模一样,直接用2186的代码修改一下就AC了。可以当作tarjan缩点的模板用了。
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 10100 #define eps 1e-7 #define INF 0x3F3F3F3F //0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 1313131 #define MOD 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int maxm = 50010; struct node{ int u, v, next; }edge[maxm]; int Stack[MAXN]; int out[MAXN]; int head[MAXN], dfn[MAXN], low[MAXN], sccno[MAXN]; int scc_cnt, id, cnt, top, n, m; void add_edge(int u, int v){ edge[cnt].u = u; edge[cnt].v = v; edge[cnt].next = head[u]; head[u] = cnt++; } void tarjin(int u){ int i, j; dfn[u] = low[u] = ++id; Stack[top++] = u; for(i = head[u]; i != -1; i = edge[i].next){ int v = edge[i].v; if(dfn[v] == -1){ tarjin(v); low[u] = min(low[u], low[v]); } else if(!sccno[v]){ low[u] = min(low[u], dfn[v]); } } if(low[u] == dfn[u]){ scc_cnt++; int temp; do{ temp = Stack[--top]; sccno[temp] = scc_cnt; }while(temp != u); } } int main(){ int i, j, t; while(scanf("%d", &n), n){ scanf("%d", &m); cnt = scc_cnt = id = top = 0; memset(head, -1, sizeof(head)); memset(dfn, -1, sizeof(dfn)); memset(sccno, 0, sizeof(sccno)); memset(out, 0, sizeof(out)); for(i = 0; i < m; i++){ int u, v; scanf("%d%d", &u, &v); add_edge(u, v); } for(i = 1; i <= n; i++){ if(dfn[i] == -1) tarjin(i); } for(i = 0; i < cnt; i++){ int u = edge[i].u; int v = edge[i].v; if(sccno[u] != sccno[v]) out[sccno[u]]++; } int flag = 0; for(i = 1; i <= n; i++){ if(out[sccno[i]] == 0){ if(flag) printf(" "); flag = 1; printf("%d", i); } } printf("\n"); } return 0; }