### Genealogical tree

Description:
The system of Martians’ blood relations is confusing enough. Actually, Martians bud when they want and where they want. They gather together in different groups, so that a Martian can have one parent as well as ten. Nobody will be surprised by a hundred of children. Martians have got used to this and their style of life seems to them natural.
And in the Planetary Council the confusing genealogical system leads to some embarrassment. There meet the worthiest of Martians, and therefore in order to offend nobody in all of the discussions it is used first to give the floor to the old Martians, than to the younger ones and only than to the most young childless assessors. However, the maintenance of this order really is not a trivial task. Not always Martian knows all of his parents (and there’s nothing to tell about his grandparents!). But if by a mistake first speak a grandson and only than his young appearing great-grandfather, this is a real scandal.
Your task is to write a program, which would define once and for all, an order that would guarantee that every member of the Council takes the floor earlier than each of his descendants.
Input

The first line of the standard input contains an only number N, 1 <= N <= 100 — a number of members of the Martian Planetary Council. According to the centuries-old tradition members of the Council are enumerated with the natural numbers from 1 up to N. Further, there are exactly N lines, moreover, the I-th line contains a list of I-th member’s children. The list of children is a sequence of serial numbers of children in a arbitrary order separated by spaces. The list of children may be empty. The list (even if it is empty) ends with 0.

Output

The standard output should contain in its only line a sequence of speakers’ numbers, separated by spaces. If several sequences satisfy the conditions of the problem, you are to write to the standard output any of them. At least one such sequence always exists.

Sample Input

5
0
4 5 1 0
1 0
5 3 0
3 0

Sample Output

2 4 5 3 1

Problem solving:

Code:

#include<iostream>
#include<cstdio>
#include<queue>

using namespace std;
int sijia[105];
vector<int> xiaozhu[105];
int main()
{
int n,m,nn,mid;
cin>>n;
nn=n;
for(int i=1;i<=n;i++)
{
while(cin>>m&&m)
{
sijia[m]++;
xiaozhu[i].push_back(m);
continue;
}
}
queue<int> q;
for(int i=1;i<=nn;i++)
{
if(sijia[i]==0)
{
q.push(i);
}
}
while(!q.empty())
{
int qixi=q.front();
q.pop();
cout<<qixi<<" ";
for(int i=0;i<xiaozhu[qixi].size();i++)
{
sijia[xiaozhu[qixi][i]]--;
if(sijia[xiaozhu[qixi][i]]==0)
q.push(xiaozhu[qixi][i]);
}
}
}

### Window Pains

Description:
Boudreaux likes to multitask, especially when it comes to using his computer. Never satisfied with just running one application at a time, he usually runs nine applications, each in its own window. Due to limited screen real estate, he overlaps these windows and brings whatever window he currently needs to work with to the foreground. If his screen were a 4 x 4 grid of squares, each of Boudreaux’s windows would be represented by the following 2 x 2 windows:

When Boudreaux brings a window to the foreground, all of its squares come to the top, overlapping any squares it shares with other windows. For example, if window 1 and then window 2 were brought to the foreground, the resulting representation would be:

Unfortunately, Boudreaux’s computer is very unreliable and crashes often. He could easily tell if a crash occurred by looking at the windows and seeing a graphical representation that should not occur if windows were being brought to the foreground correctly. And this is where you come in . . .
Input

Input to this problem will consist of a (non-empty) series of up to 100 data sets. Each data set will be formatted according to the following description, and there will be no blank lines separating data sets.
A single data set has 3 components:
Start line - A single line:
START
Screen Shot - Four lines that represent the current graphical representation of the windows on Boudreaux’s screen. Each position in this 4 x 4 matrix will represent the current piece of window showing in each square. To make input easier, the list of numbers on each line will be delimited by a single space.
End line - A single line:
END
After the last data set, there will be a single line:
ENDOFINPUT
Note that each piece of visible window will appear only in screen areas where the window could appear when brought to the front. For instance, a 1 can only appear in the top left quadrant.

Output

For each data set, there will be exactly one line of output. If there exists a sequence of bringing windows to the foreground that would result in the graphical representation of the windows on Boudreaux’s screen, the output will be a single line with the statement:
THESE WINDOWS ARE CLEAN
Otherwise, the output will be a single line with the statement:
THESE WINDOWS ARE BROKEN

Sample Input

START
1 2 3 3
4 5 6 6
7 8 9 9
7 8 9 9
END
START
1 1 3 3
4 1 3 3
7 7 9 9
7 7 9 9
END
ENDOFINPUT

Sample Output

THESE WINDOWS ARE CLEAN
THESE WINDOWS ARE BROKEN

Problem solving:

Code:

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#include<cstring>
using namespace std;
int ma[10][10],sijia[10];
int dr[]={0,1,0,1},dc[]={0,0,1,1};
vector<int> ve[10][10];
bool solve()
{
queue<int> q;
for(int i=0;i<9;i++)
if(sijia[i]==0) q.push(i);
int sum=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int v=0;v<9;v++)
{
if(ma[u][v])
{
ma[u][v]=0;
sijia[v]--;
if(sijia[v]==0)   q.push(v);
}
}
sum++;
}
return sum==9;
}
int main()
{
for(int i=0;i<9;i++)
{
int r=i/3,c=i%3;
for(int j=0;j<4;j++)
{
int nr=r+dr[j],nc=c+dc[j];
ve[nr][nc].push_back(i);
}
}
string s;
while(cin>>s&&s[0]!='E')
{
memset(ma,0,sizeof(ma));
memset(sijia,0,sizeof(sijia));
for(int i=0;i<4;i++)
{
for(int j=0;j<4;j++)
{
int v;
cin>>v;
v--;
for(int k=0;k<ve[i][j].size();k++)
{
if(ve[i][j][k]!=v)
{
int x=ve[i][j][k];
if(ma[x][v]==0)
{
sijia[v]++;
ma[x][v]=1;
}
}
}
}
}
if(solve()) puts("THESE WINDOWS ARE CLEAN");
else    puts("THESE WINDOWS ARE BROKEN");
cin>>s;
}
}

### 确定比赛名次

Description:

Input

Output

Sample Input

4 3
1 2
2 3
4 3

Sample Output

1 2 4 3

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
const int sijiaxiaozhu=521;
int qixikuaile[sijiaxiaozhu];
vector<int> yongyuan[sijiaxiaozhu];
int main()
{
int n,m,x,y;
while(cin>>n>>m)
{
memset(qixikuaile,0,sizeof(qixikuaile));
for(int i=0;i<=n;i++) yongyuan[i].clear();
for(int i=0;i<m;i++)
{
cin>>x>>y;
qixikuaile[y]++;
yongyuan[x].push_back(y);
}

priority_queue<int,vector<int>,greater<int> > q ;
int flag=1;
for(int i=1;i<=n;i++)
{
if(qixikuaile[i]==0)  q.push(i);
}
while(!q.empty())
{
int mid=q.top();
q.pop();
if(flag)
{
cout<<mid;
flag=0;
}
else  cout<<" "<<mid;
for(int i=0;i<yongyuan[mid].size();i++)
{
qixikuaile[yongyuan[mid][i]]--;
if(qixikuaile[yongyuan[mid][i]]==0) q.push(yongyuan[mid][i]);
}
}
cout<<endl;
}
return 0;
}

### 产生冠军

Description:

Input

Output

Sample Input

3
Alice Bob
Smith John
Alice Smith
5
a c
c d
d e
b e
a d
0

Sample Output

Yes
No

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
string x,y;
while(cin>>n&&n)
{
set<string> sijia;
set<string> xiaozhu;
for(int i=0;i<n;i++)
{
cin>>x>>y;
sijia.insert(x),sijia.insert(y);
xiaozhu.insert(y);
}
if(sijia.size()-xiaozhu.size()==1)  puts("Yes");
else    puts("No");
}
}

Description:
ACM-DIY is a large QQ group where many excellent acmers get together. It is so harmonious that just like a big family. Every day,many “holy cows” like HH, hh, AC, ZT, lcc, BF, Qinz and so on chat on-line to exchange their ideas. When someone has questions, many warm-hearted cows like Lost will come to help. Then the one being helped will call Lost “master”, and Lost will have a nice “prentice”. By and by, there are many pairs of “master and prentice”. But then problem occurs: there are too many masters and too many prentices, how can we know whether it is legal or not?

We all know a master can have many prentices and a prentice may have a lot of masters too, it’s legal. Nevertheless，some cows are not so honest, they hold illegal relationship. Take HH and 3xian for instant, HH is 3xian’s master and, at the same time, 3xian is HH’s master,which is quite illegal! To avoid this,please help us to judge whether their relationship is legal or not.

Please note that the “master and prentice” relation is transitive. It means that if A is B’s master ans B is C’s master, then A is C’s master.
Input

The input consists of several test cases. For each case, the first line contains two integers, N (members to be tested) and M (relationships to be tested)(2 <= N, M <= 100). Then M lines follow, each contains a pair of (x, y) which means x is y’s master and y is x’s prentice. The input is terminated by N = 0.
TO MAKE IT SIMPLE, we give every one a number (0, 1, 2,…, N-1). We use their numbers instead of their names.

Output

For each test case, print in one line the judgement of the messy relationship.
If it is legal, output “YES”, otherwise “NO”.

Sample Input

3 2
0 1
1 2
2 2
0 1
1 0
0 0

Sample Output

YES
NO

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
int sijia[521];
vector<int> xiaozhu[521];
int main()
{
int n,m,a,b;
while(cin>>n>>m)
{
memset(sijia,0,sizeof(sijia));
for(int i=0;i<=n;i++  )    xiaozhu[i].clear();
if(n==0&&m==0)  break;
for(int i=0;i<m;i++)
{
cin>>a>>b;
sijia[b]++;
xiaozhu[a].push_back(b);
}
queue<int> q;
for(int i=0;i<n;i++)
{
if(sijia[i]==0)
q.push(i);
}
while(!q.empty())
{
int mid=q.front();
q.pop();
n--;
for(int i=0;i<xiaozhu[mid].size();i++)
{
sijia[xiaozhu[mid][i]]--;
if(sijia[xiaozhu[mid][i]]==0)
q.push(xiaozhu[mid][i]);
}
}
if(n)   puts("NO");//如果n不为0，说明成环
else    puts("YES");
}
}

### Reward

Description:
Dandelion’s uncle is a boss of a factory. As the spring festival is coming , he wants to distribute rewards to his workers. Now he has a trouble about how to distribute the rewards.
The workers will compare their rewards ,and some one may have demands of the distributing of rewards ,just like a’s reward should more than b’s.Dandelion’s unclue wants to fulfill all the demands, of course ,he wants to use the least money.Every work’s reward will be at least 888 , because it’s a lucky number.
Input

One line with two integers n and m ,stands for the number of works and the number of demands .(n<=10000,m<=20000)
then m lines ,each line contains two integers a and b ,stands for a’s reward should be more than b’s.

Output

For every case ,print the least money dandelion ‘s uncle needs to distribute .If it’s impossible to fulfill all the works’ demands ,print -1.

Sample Input

2 1
1 2
2 2
1 2
2 1

Sample Output

1777
-1

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
#define maxn 10000
queue<int> q;
vector<int>t[10005];
int in[10005],sum[10005],cnt,u,v,ans;
void Init()
{
for(int i=0;i<maxn;i++)
t[i].clear();
while(!q.empty())
q.pop();
memset(in,0,sizeof(in));
ans=0;
}

int main()
{
int n,m;
while(cin>>n>>m)
{
Init();
for(int i=0;i<m;i++)
{
cin>>u>>v;
u--;v--;
in[u]++;
t[v].push_back(u);
}
for(int i=0;i<n;i++)
{
if(!in[i])
{
q.push(i);
sum[i]=888;
}
}
cnt=0;
while(!q.empty())
{
cnt++;
int p=q.front();
q.pop();
for(int i=0;i<t[p].size();i++)
{
in[t[p][i]]--;
if(in[t[p][i]]==0)
{
q.push(t[p][i]);
sum[t[p][i]]=sum[p]+1;    //对工资的处理
}
}
}
for(int i=0;i<n;i++)
ans+=sum[i];
if(cnt!=n)
ans=-1;
cout<<ans<<endl;
}
return 0;
}

PDF题面:七夕快乐
Description:
John has n tasks to do. Unfortunately, the tasks are not independent and the execution of one task is
Input

The input will consist of several instances of the problem. Each instance begins with a line containing
two integers, 1 ≤ n ≤ 100 and m. n is the number of tasks (numbered from 1 to n) and m is the
number of direct precedence relations between tasks. After this, there will be m lines with two integers
i and j, representing the fact that task i must be executed before task j.
An instance with n = m = 0 will finish the input.

Output

For each instance, print a line with n integers representing the tasks in a possible order of execution.

Sample Input

5 4
1 2
2 3
1 3
1 5
0 0

Sample Output

1 4 2 5 3

Problem solving:

Code:

#include<bits/stdc++.h>
using namespace std;
int sijia[105];
vector<int> xiaozhu[105];
int n,m,x,y;
int main()
{
while(cin>>n>>m)
{
memset(sijia,0,sizeof(sijia));
for(int i=0;i<=n;i++)   xiaozhu[i].clear();
if(n==0&&m==0)  break;
for(int i=0;i<m;i++)
{
cin>>x>>y;
sijia[y]++;
xiaozhu[x].push_back(y);
}
queue<int> qixi;
for(int i=1;i<=n;i++)
{
if(sijia[i]==0) qixi.push(i);
}
while(!qixi.empty())
{
int kuaile=qixi.front();
qixi.pop();
cout<<kuaile<<" ";
for(int i=0;i<xiaozhu[kuaile].size();i++)
{
sijia[xiaozhu[kuaile][i]]--;
if(sijia[xiaozhu[kuaile][i]]==0)
qixi.push(xiaozhu[kuaile][i]);
}
}
cout<<endl;
}
}

### Rank of Tetris

Description:

Input

Output

Sample Input

3 3
0 > 1
1 < 2
0 > 2
4 4
1 = 2
1 > 3
2 > 0
0 > 1
3 3
1 > 0
1 > 2
2 < 1

Sample Output

OK
CONFLICT
UNCERTAIN

Problem solving:

CONFLICT就是有了冲突，有了冲突是什么情况呢？就是存的图里面出现了有环存在的情况，也就是最后还有入度不为0的结点存在。
UNCERTAIN就是不确定，不确定是什么情况呢？就是有两个节点的大小关系不知道，也就是存着入度为0的节点的队列中存在两个以上的节点，这个应该还挺好理解的，如果在同一次循环中出现了两个入度为0的节点，说明这两个点之间没有任何边连接着，所以他俩的大小关系自然是不确定了。

Code:

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
int n,m,sijia[52121],p[52121],sum;
vector<int> ma[52121];
struct node{
int x,y;
char s;
}xiaozhu[52121];
int find(int x)
{
return p[x]!=x?p[x]=find(p[x]):x;//并查集的查找函数
}
bool join(int x,int y)//并查集的合并函数，这里设置成bool类型是为了下面方便
{
x=find(x),y=find(y);
if(x==y)//如果x和y的父节点已经相等了，就不用在处理了
return 0;
p[x]=y;
return 1;
}
void solve()//拓扑排序
{
queue<int> q;
for(int i=0;i<n;i++)
{
if(p[i]==i&&sijia[i]==0)    q.push(i);
}
int flag=0;
while(!q.empty())
{
if(q.size()>1)  flag=1;   //入度为0的点同时出现了两个
int mid=q.front();
q.pop();sum--;
for(int i=0;i<ma[mid].size();i++)
{
sijia[ma[mid][i]]--;
if(sijia[ma[mid][i]]==0)    q.push(ma[mid][i]);
}
}
if(sum>0)   puts("CONFLICT");  //有环存在
else if(flag)   puts("UNCERTAIN");//sum大于0说明同一等级上不是只有唯一的一个
else    puts("OK");
}
int main()
{
while(cin>>n>>m)
{
memset(sijia,0,sizeof(sijia));
memset(ma,0,sizeof(ma));
sum=n;
for(int i=0;i<n;i++)    p[i]=i;
for(int i=0;i<m;i++)
{
cin>>xiaozhu[i].x>>xiaozhu[i].s>>xiaozhu[i].y;
if(xiaozhu[i].s=='=')//如果出现了等号，就把两个合并
{
if(join(xiaozhu[i].x,xiaozhu[i].y))
{
sum--;//因为合并起来了两个，所以总的拓扑排序用到的节点数减一
}
}
}
for(int i=0;i<m;i++)//存图
{
if(xiaozhu[i].s=='=')   continue;
int xx=find(xiaozhu[i].x),yy=find(xiaozhu[i].y);
if(xiaozhu[i].s=='>')
{
ma[xx].push_back(yy);
sijia[yy]++;
}
else
{
ma[yy].push_back(xx);
sijia[xx]++;
}
}
solve();
}
}