/*
user: php
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2756
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#include<utility>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define dd double
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod abs
#define pf printf
#define sf scanf
#define mp make_pair
#define paii pair<int, int>
#define padd pair<dd, dd>
#define pall pair<ll, ll>
#define fr first
#define sc second
using namespace std;
#define MAXX 1002
map<string, int> mapping;
vector<int>graph[MAXX];
bool visited[MAXX][MAXX];
bool used[MAXX];
int P, T;
void dfs(int u, int v)
{
visited[u][v] = 1;
int vv;
loop(i, SZ(graph[v]))
{
vv = graph[v][i];
if(!visited[u][vv])
{
dfs(u, vv);
}
}
}
int main()
{
//string str1, str2;
char finput[25], sinput[25];
int cnt;
while(1)
{
getint(P); getint(T);
if(P == 0 && T == 0) break;
mapping.clear();
cin.ignore();
loop(i, P)
{
graph[i].clear();
//getline(cin, str1);
gets(finput);
mapping[finput] = i;
}
loop(i, T)
{
//getline(cin, str1);
//getline(cin, str2);
gets(finput);
gets(sinput);
graph[ mapping[finput] ].pb(mapping[sinput]);
}
mem(visited, 0);
loop(i, P) dfs(i, i);
mem(used, 0);
cnt = 0;
loop(i, P)
{
if(!used[i])
{
cnt++;
FOR(j, i+1, P)
{
if( !used[j] && visited[i][j] && visited[j][i] )
{
used[j] = 1;
}
}
}
}
pf("%d\n", cnt);
}
return 0;
}
Category Archives: STL
(UVa) 10608 – Friends
0
/*
user: php
time: 0.048 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1549
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<sstream>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define getint(n) scanf("%d", &n)
#define pb(a) push_back(a)
#define ll long long
#define SZ(a) int(a.size())
#define read() freopen("input.txt", "r", stdin)
#define write() freopen("output.txt", "w", stdout)
#define mem(a, v) memset(a, v, sizeof(a))
#define all(v) v.begin(), v.end()
#define pi acos(-1.0)
#define INF 1<<29
#define mod(a) (a>0?a:-a)
#define pf printf
#define sf scanf
using namespace std;
#define MAXX 50002
int parent[MAXX];
int find(int u)
{
if(parent[u] == u) return u;
return parent[u] = find(parent[u]);
}
int main()
{
int n, m;
int p, q;
int kaseno = 0, kases;
getint(kases);
while(kases--)
{
getint(n); getint(m);
for(int i=1; i<=n; i++)
{
parent[i] = i;
}
loop(i, m)
{
getint(p); getint(q);
p = find(p);
q = find(q);
parent[p] = q;
}
map<int ,int>mp;
int *p;
int maxcircle = 0;
for(int i=1; i<=n; i++)
{
p = &mp[find(i)];
(*p)++;
maxcircle = max(maxcircle, *p);
}
pf("%d\n", maxcircle);
}
return 0;
}
(LightOj) 1003 – Drunk
0
/*
user: php
time: 0.244 sec
link: http://lightoj.com/volume_showproblem.php?problem=1003
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<map>
#include<stack>
#include<queue>
#include<string>
#include<vector>
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define loop(i, n) for(int i=0; i<n; i++)
#define mem(a, v) memset(a, v, sizeof(a))
#define PI acos(-1.0)
#define INF 1<<29
#define SZ size()
#define all(v) v.begin(), v.end()
#define pb(a) push_back(a)
#define ll long long
#define READ() freopen("input.txt", "r", stdin)
#define WRITE() freopen("output.txt", "w", stdout)
#define geti(n) scanf("%d", &n)
#define getii(a, b) scanf("%d %d", &a, &b)
using namespace std;
int main()
{
int kases, query, kaseno = 0;
string a, b;
map<string, vector<string> > mp;
map<string, int> weight;
map<string, bool> all;
map<string, bool>::iterator it;
vector<string> *v;
int *p;
bool drunk;
vector<string>zero;
geti(kases);
while(kases--)
{
mp.clear();
weight.clear();
zero.clear();
all.clear();
geti(query);
loop(i, query)
{
cin>>a>>b;
all[a] = 0;
all[b] = 0;
mp[a].pb(b);
weight[b]++;
}
for(it = all.begin(); it != all.end(); it++)
{
a = it->first;
if(weight[a] == 0)
zero.pb(a);
}
loop(i, zero.SZ)
{
a = zero[i];
v = &mp[a];
loop(j, v->SZ)
{
b = (*v)[j];
p = &weight[b];
(*p)--;
if((*p) == 0)
{
zero.pb(b);
}
}
}
drunk = true;
for(it = all.begin(); it != all.end(); it++)
{
a = it->first;
if(weight[a] != 0)
{
drunk = false;
break;
}
}
if(drunk)
{
printf("Case %d: Yes\n", ++kaseno);
}
else
{
printf("Case %d: No\n", ++kaseno);
}
}
return 0;
}
(UVa) 11060 – Beverages
0
/*
user: php
time: 0.020 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2001
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#define getint(a) scanf("%d", &a)
#define loop(i, n) for(int i=0; i<n; i++)
#define FOR(i, s, e) for(int i=s; i<e; i++)
#define pb(a) push_back(a)
#define SZ size()
using namespace std;
map<string, int> pos;
struct compare{
bool operator () (string a, string b)
{
return pos[a] > pos[b];
}
};
vector<string>beverages;
map<string, vector<string> > graph;
map<string, int>weight;
priority_queue<string, vector<string>, compare> zeroWeight;
vector<string>list;
int main()
{
string p, q;
int *point;
int kaseno = 0;
int bevarage_number, connections;
while(getint(bevarage_number) == 1)
{
weight.clear();
while(zeroWeight.SZ)
{
zeroWeight.pop();
}
list.clear();
beverages.clear();
graph.clear();
loop(i, bevarage_number)
{
cin>>p;
beverages.pb(p);
pos[p] = i;
}
getint(connections);
loop(i, connections)
{
cin>>p;
cin>>q;
graph[p].pb(q);
weight[q]++;
}
loop(i, bevarage_number)
{
p = beverages[i];
if(weight[p] == 0)
{
zeroWeight.push(p);
}
}
loop(i, bevarage_number)
{
p = zeroWeight.top();
zeroWeight.pop();
list.pb(p);
loop(j, graph[p].SZ)
{
q = graph[p][j];
point = &weight[q];
(*point)--;
if(*point == 0)
{
zeroWeight.push(q);
}
}
}
printf("Case #%d: Dilbert should drink beverages in this order: %s", ++kaseno, list[0].c_str());
FOR(i, 1, bevarage_number)
{
cout<<" "<<list[i];
}
printf(".\n\n");
}
}
(UVa) 902 – Password Search
0
/*
user: php
time: 1.828 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=843
*/
#include<iostream>
#include<string>
#include<map>
#include<cstdio>
using namespace std;
int main()
{
int maxCount, passwordLength, end;
string text, temp;
string maxPass;
int *p;
map<string, int>mp;
while(cin>>passwordLength>>text)
{
mp.clear();
maxCount = -1;
end = text.length() - passwordLength+1;
for(int i=0; i<end; i++)
{
temp = text.substr(i, passwordLength);
p = &mp[temp];
(*p)++;
if(*p > maxCount)
{
maxCount = *p;
maxPass = temp;
}
}
printf("%s\n", maxPass.c_str());
}
}
(UVa) 350 – Pseudo-Random Numbers
0
/*
user: php
time: 0.060 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=286
*/
#include<iostream>
#include<cstdio>
#include<map>
#define get(a) scanf("%d", &a)
using namespace std;
int main()
{
map<int, bool>mp;
int random, mul, add, mod, seed;
int kaseno = 0;
bool *t;
while(true)
{
get(mul);
get(add);
get(mod);
get(random);
if(mul == 0 && add == 0 && mod == 0 && random == 0 ) break;
seed = random;
mp.clear();
while(true)
{
t = &mp[random];
if(*t == true) break;
*t = true;
random = (random * mul + add) % mod;
}
printf("Case %d: %d\n", ++kaseno, mp.size() - (random!=seed));
}
}
(LightOj) 1009 – Back to Underworld
0
/*
user: php
time: 0.312 sec
link: http://lightoj.com/volume_showproblem.php?problem=1009
*/
#include<iostream>
#include<vector>
#include<cstdio>
#define getint(a) scanf("%d", &a)
#define loop(i, n) for(int i=0; i<n; i++)
#define pb push_back
#define MAXX 20001
using namespace std;
vector<int>Graph[MAXX];
bool visited[MAXX];
bool nodeAdded[MAXX];
vector<int>nodeList;
int bfs(int source)
{
int level[2];
level[0] = 0;
level[1] = 0;
int current_level = 0;
int size;
int u, v;
int len;
visited = true;
vector<int>v1, v2;
v1.pb(source);
level[current_level]++;
while(!v1.empty())
{
current_level = (current_level + 1) % 2;
size = v1.size();
loop(i, size)
{
u = v1[i];
len = Graph[u].size();
loop(j, len)
{
v = Graph[u][j];
if(!visited[v])
{
v2.pb(v);
visited[v] = true;
level[current_level]++;
}
}
}
v1.clear();
v1 = v2;
v2.clear();
}
return level[0] > level[1]? level[0] : level[1];
}
int main()
{
int kases, duel_fights_numbers, u, v, kaseno=0, max;
getint(kases);
while(kases--)
{
nodeList.clear();
max = 0;
loop(i, MAXX)
{
Graph[i].clear();
visited[i] = false;
}
getint(duel_fights_numbers);
loop(i, duel_fights_numbers)
{
getint(u); getint(v);
Graph[u].pb(v);
Graph[v].pb(u);
if(!nodeAdded[u])
{
nodeList.pb(u);
nodeAdded[u] = true;
}
if(!nodeAdded[v])
{
nodeList.pb(v);
nodeAdded[v] = true;
}
}
int len = nodeList.size();
loop(i, len)
{
u = nodeList[i];
if(!visited[u])
{
max += bfs(u);
}
nodeAdded[u] = false;
}
printf("Case %d: %d\n", ++kaseno, max);
}
}
(UVa) 10147 – Highways
0
/*
user: php
time: 0.444 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1088
*/
#include<iostream>
#include<vector>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define getint(n) scanf("%d", &n)
#define loop(i, n) for(int i=0; i<n; i++)
using namespace std;
long long square(int a)
{
return (long long)a * (long long)a;
}
struct plot{
int x, y;
};
plot point[751];
struct distances{
int from, to;
double dist;
void push(int a, int b)
{
from = a;
to = b;
dist = sqrt(square(point[a].x - point[b].x) + square(point[a].y - point[b].y));
}
};
int parent[751];
distances di[281250];
int find(int townID)
{
if(parent[townID] == townID)
{
return townID;
}
return parent[townID] = find(parent[townID]);
}
bool comp(distances a, distances b)
{
return a.dist < b.dist;
}
int main()
{
int kases, towns, x, y, existingHighWays, p;
bool all_connected;
getint(kases);
while(kases--)
{
all_connected = true;
getint(towns);
loop(t, towns)
{
getint(x);
getint(y);
point[t].x = x;
point[t].y = y;
}
loop(i, 751)
{
parent[i] = i;
}
getint(existingHighWays);
loop(t, existingHighWays)
{
getint(x); //x'th highway and y'th highway are connected
getint(y);
x = find(x-1);
y = find(y-1);
parent[x] = y;
}
p = 0;
loop(i, towns)
{
for(int j=i+1; j<towns; j++)
{
if(find(i) != find(j))
{//they are not yet connected some how
di[p++].push(i, j);
}
}
}
sort(di, di + p, comp);
loop(i, p)
{
x = find(di[i].from);
y = find(di[i].to);
if(x != y)
{
all_connected = false;
parent[x] = y;
printf("%d %d\n", di[i].from+1, di[i].to+1);
}
}
if(all_connected)
{
printf("No new highways need\n");
}
if(kases) printf("\n");
}
return 0;
}
(UVa) 544 – Heavy Cargo
0
/*
user: php
time: 0.040 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=485
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
#define getint(a) scanf("%d", &a)
#define loop(i, n) for(int i=0; i<n; i++)
using namespace std;
map<string, string> parent;
struct DATA{
string u, v;
int weight;
};
bool comp(DATA a, DATA b)
{
return a.weight > b.weight;
}
string find(string str)
{
if(parent[str] == "")
{
return str;
}
return parent[str] = find(parent[str]);
}
int main()
{
int number_of_cities, number_of_roads;
string city1, city2;
int weight;
DATA edge;
int minValue;
int kaseno = 0;
string u, v;
vector<DATA> edgelist;
while(true)
{
getint(number_of_cities);
getint(number_of_roads);
if(number_of_cities == 0 && number_of_roads == 0) break;
parent.clear();
edgelist.clear();
loop(t, number_of_roads)
{
cin>>city1>>city2>>weight;
edge.u = city1;
edge.v = city2;
edge.weight = weight;
edgelist.push_back(edge);
}
cin>>city1>>city2;
sort(edgelist.begin(), edgelist.end(), comp);
minValue = 1000000;
loop(i, number_of_roads)
{
u = find(edgelist[i].u);
v = find(edgelist[i].v);
if(u != v)
{
parent[u] = v;
if(minValue > edgelist[i].weight )
{
minValue = edgelist[i].weight;
}
}
if(find(city1) == find(city2))
{
break;
}
}
printf("Scenario #%d\n", ++kaseno);
printf("%d tons\n\n", minValue);
}
return 0;
}
(UVa) 11239 – Open Source
0
/*
user: php
time: 0.016 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2180
*/
#include<iostream>
#include<map>
#include<string>
#include<algorithm>
#include<cstdio>
using namespace std;
struct Team{
string projectName;
int students;
};
map<string, int>studentVSproject;
Team project[102];
bool compare(Team a, Team b)
{
if(a.students > b.students) return true;
if(a.students < b.students) return false;
if(a.projectName < b.projectName) return true;
return false;
}
int main()
{
string input;
int temp;
int project_iterator = 0;
while(getline(cin, input))
{
if(input == "0")
{
break;
}
if( input != "1")
{
if('A' <= input[0] && input[0] <='Z' )
{// it's team name;
project[project_iterator].projectName = input;
project[project_iterator].students = 0;
project_iterator++;
}
else
{//it's userid
temp = studentVSproject[input];
if(temp == 0)
{//new student who has not yet submit anywhere
studentVSproject[input] = project_iterator;
project[project_iterator - 1].students++;
}
else if(temp < 150 && temp != project_iterator)
{
project[temp-1].students--;
studentVSproject[input] = 500;
}
}
}
else
{
sort(project, project+project_iterator, compare);
for(int i=0; i<project_iterator; i++)
{
printf("%s %d\n", project[i].projectName.c_str(), project[i].students);
}
project_iterator = 0;
studentVSproject.clear();
}
}
return 0;
}
UnLucky Codes 