#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=100005;
struct Node{
int address;
int data;
int next;
bool flags=false;
}node[maxn];
bool cmp(Node a,Node b){
if(a.flags>b.flags){//1
return true;
}else{
return a.data<b.data;
}
}
int main(){
int num,head,ad;
scanf("%d%d",&num,&head);
for(int i=0;i<num;i++){
scanf("%d%d%d",&ad,&node[ad].data,&node[ad].next);//2
node[ad].address=ad;
}
int active=head;
int count=0;
while(active!=-1){
node[active].flags=true;
active=node[active].next;
count++;
}
if(count==0){
printf("0 -1\n");
}else{
sort(node,node+maxn,cmp);
printf("%d d\n",count,node[0].address);
for(int i=0;i<count;i++){
printf("d %d",node[i].address,node[i].data);
if(i==count-1){
printf(" -1\n");
}
else{
printf(" d\n",node[i+1].address);
}
}
}
return 0;
}
/*将标记2的地方修改为：
scanf("%d",&ad);
scanf("%d%d",&node[ad].data,&node[ad].next);
//from liuchuo:
#include <cstdio>
#include <algorithm>
using namespace std;
struct NODE {
int address;
int key;
int next;
bool flag;
}node[100000];
int cmp1(NODE a, NODE b) {
if(a.flag == false || b.flag == false) {
return a.flag > b.flag;
} else {
return a.key < b.key;
}
}
int main() {
int n, cnt = 0, s, a, b, c;
scanf("%d%d", &n, &s);
for(int i = 0; i < n; i++) {
scanf("%d%d%d", &a, &b, &c);
node[a].address = a;
node[a].key = b;
node[a].next = c;
}
for(int i = s; i != -1; i = node[i].next) {
node[i].flag = true;
cnt++;
}
if(cnt == 0) {
printf("0 -1");
} else {
sort(node, node + 100000, cmp1);
printf("%d d\n", cnt, node[0].address);
for(int i = 0; i < cnt; i++) {
printf("d %d ", node[i].address, node[i].key);
if(i != cnt - 1)
printf("d\n", node[i + 1].address);
else
printf("-1\n");
}
}
return 0;
}
//My::错误百出第一版，越改越错，码生昏暗
#include<cstdio>
#include<algorithm>
using namespace std;
struct Node{
int address;
int data;
int next;
bool flags=false;
}node[100005];
bool cmp(Node a,Node b){
if(a.flags>b.flags){
return true;
}//这里错了！！cmp只能用if-else-if.不能有两个if!!
if(a.flags==true&&b.flags==true){
return a.data<b.data;
}
}
int main(){
int num,head,ad;
scanf("%d%d",&num,&head);
for(int i=0;i<num;i++){
scanf("%d%d%d",&ad,&node[ad].data,&node[ad].next);
node[ad].address=ad;
}
int active=head;
int count=0;
while(active!=-1){
node[active].flags=true;
active=node[active].next;
count++;
}
/* while(active!=-1){
for(int i=0;i<num;i++){
if(active==node[i].address){
node[i].flags=true;
active=node[i].next;
count++;
break;
}
}
}这种写法运行超时了*/
if(count==0){/*判断空链表!!!*/
printf("0 -1\n");
}else{
sort(node,node+100005,cmp);/*因为前面将改写成了随机存取，所以这里要对整张链表排序*/
printf("%d d\n",count,node[0].address);
for(int i=0;i<count;i++){
printf("d %d",node[i].address,node[i].data);
if(i==count-1){
printf(" -1\n");
}
else{
printf(" d\n",node[i+1].address);
}
}
}
return 0;
}//
段错误，答案错误，运行超时……快凑齐了
//段错误一般是内存越界。//由版本一修改而来的错误百出版本二：这是有两个错误点的代码：得到结果：
段错误没了，*/将标记1的地方修改为:
if(a.flags==false||b.flags==false){//1
return a.flags>b.flags;
后经测试：错误点cmp函数也会引起段错误。已经用了很长时间，故不再研究。总结：1.严格规范编写cmp;注意只能有一个if,return一定是不等式。2.连续两个输入，后一个输入需要用到前一个的结果，那就用两次scanf()。全写在一个里会爆段错误。3.注意时间复杂度，空间换时间。有m个数，求m中的数在另外n个数中是否出现：hash表的时间复杂度是O(n+m)(n次存入，m次匹配)。用二层迭代就是O(n*m).4.有链表的题注意判断无效节点，判断链表是否为空。
