Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

有点懒,547ms,STL是慢啊

Posted by KatrineYang at 2016-07-23 21:58:08 on Problem 1144 and last updated at 2016-07-23 21:58:26
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator