| ||||||||||
| 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