Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
有点懒,547ms,STL是慢啊#include <iostream> #include <stdio.h> #include <cstring> #include <vector> #include <queue> using namespace std; int main() { while(1){ int N; scanf("%d", &N); if(N == 0) break; vector<int> conn[101]; bool mtx[101][101] = {0}; while(1){ char c[256]; gets(c); if(c[0] == '0') break; int cf; int len = strlen(c); int ks; if(c[1] == ' '){ cf = c[0] - '0'; ks = 2; } else{ cf = (c[0]-'0') * 10 + (c[1]-'0'); ks = 3; } while(ks < len){ int xc; if(ks < len-1 && c[ks+1] != ' '){ xc = (c[ks] - '0')*10 + (c[ks+1]-'0'); ks += 3; } else{ xc = c[ks]-'0'; ks += 2; } conn[cf].push_back(xc); mtx[cf][xc] = 1; if(!mtx[xc][cf]){ mtx[xc][cf] = 1; conn[xc].push_back(cf); } } } if(N < 3){ printf("0\n"); continue; } int cnt = 0; for(int crit = 1; crit <= N; crit ++){ if(conn[crit].size() <= 1) continue; int size = conn[crit].size(); bool visited[101] = {false}; int start = conn[crit][0]; queue<int> bfs; bfs.push(start); visited[start] = true; while(!bfs.empty()){ int TB = bfs.front(); bfs.pop(); int gs = conn[TB].size(); for(int i = 0; i < gs; i++){ int toPush = conn[TB][i]; if(!visited[toPush] && toPush != crit){ visited[toPush] = true; bfs.push(toPush); } } } for(int i = 1; i < size; i++){ if(!visited[conn[crit][i]]){ cnt ++; break; } } } printf("%d\n", cnt); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator