/*
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;
}
Category Archives: Topological Sort
(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) 10305 – Ordering Tasks
0
/*
user: php
time: 0.008 sec
link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1246
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#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 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)
using namespace std;
vector<int> graph[101];
int weight[101];
vector<int> zeroWeighted;
int main()
{
int n, m;
int p, q;
while(scanf("%d %d", &n, &m) == 2 && (n!=0 || m!=0))
{
loop(i, 101)
{
graph[i].clear();
weight[i] = 0;
zeroWeighted.clear();
}
loop(i, m)
{
getint(p); getint(q);
graph[p].pb(q);
weight[q]++;
}
for(int i=1; i<=n; i++)
{
if(weight[i] == 0)
{
zeroWeighted.pb(i);
}
}
loop(i, zeroWeighted.SZ)
{
p = zeroWeighted[i];
loop(j, graph[p].SZ)
{
q = graph[p][j];
weight[q]--;
if(weight[q] == 0)
{
zeroWeighted.pb(q);
}
}
}
printf("%d", zeroWeighted[0]);
FOR(i, 1, zeroWeighted.SZ)
{
printf(" %d", zeroWeighted[i]);
}
printf("\n");
}
return 0;
}
UnLucky Codes 