排序
直接插入排序
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[10]= {1,8,5,7,2,6,3,4,11,9};
int j;
for(int i = 1;i<10;i++){
if(a[i]>a[i-1]) continue;
int temp = a[i];
for( j = i-1;a[j]>temp;j--){
a[j+1] = a[j];
}
a[j+1]=temp;
}
for(int i = 0;i<10;i++){
printf("%d ",a[i]);
}
return 0;
}
空间效率O（1），时间效率O（n2），稳定。
折半插入排序
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[10]= {1,8,5,7,2,6,3,4,11,9};
int j;
for(int i = 1;i<10;i++){
if(a[i]>a[i-1]) continue;
int temp = a[i];
int low=0,high=i-1;
int mid ;
while(low<=high){
mid = (low+high)/2;
if(a[mid]>temp){
high = mid-1;
}
else low= mid+ 1 ;
}
for( j =i-1;j>=low;j--){
a[j+1] =a[j];
}
a[j+1] = temp;
}
for(int i = 0;i<10;i++){
printf("%d ",a[i]);
}
return 0;
}
空间效率O（1），时间效率O（n2），稳定。
冒泡排序
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[10]= {1,8,5,7,2,6,3,4,11,9};
for(int i = 0;i<9;i++){
for(int j = 0;j<9-i;j++){
if(a[j]>a[j+1]) swap(a[j],a[j+1]);
}
}
for(int i = 0;i<10;i++){
printf("%d ",a[i]);
}
return 0;
}
空间效率O（1），时间效率O（n2），稳定。
快速排序
#include<bits/stdc++.h>
using namespace std;
int findPivot(int a[],int left ,int right){
int temp = a[left];
while(left<right){
while(a[right]>temp&&left<right) right--;
a[left] = a[right];
while(a[left]<temp&&left<right) left++;
a[right]=a[left];
}
a[left] = temp;
return left;
}
void QuickSort(int a[],int left ,int right){
if(left<right){
int pivot = findPivot(a,left,right);
QuickSort(a,left,pivot-1);
QuickSort(a,pivot+1,right);
}
}
int main(){
int a[10]= {1,8,5,7,2,6,3,4,11,9};
QuickSort(a,0,9);
for(int i = 0;i<10;i++){
printf("%d ",a[i]);
}
return 0;
}
空间效率O（logN），时间效率O（n*logN），不稳定。
简单选择排序
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[10]= {1,8,5,7,2,6,3,4,11,9};
for(int i = 0;i<9;i++){
int minIndex=i;
for(int j=i+1;j<10;j++){
if(a[minIndex]>a[j]) minIndex = j;
}
swap(a[i],a[minIndex]);
}
for(int i = 0;i<10;i++){
printf("%d ",a[i]);
}
return 0;
}
空间效率O（1），时间效率O（n2），不稳定。
堆排序
#include<bits/stdc++.h>
using namespace std;
void adjust(int a[],int k,int len){
a[0]=a[k];
for(int i = 2*k;i<=len;i*=2){
if(a[i]<a[i+1]&&i<len) i++;
if(a[0]>=a[i]) break;
else {
a[k]=a[i];
k=i;
}
}
a[k] = a[0];
}
void BuildHeap(int a[],int len){
for(int i = len/2;i>0;i--){
adjust(a,i,len);
}
}
void HeapSort(int a[],int len){
BuildHeap(a,len);
for(int i=len;i>1;i--){
swap(a[i],a[1]);
adjust(a,1,i-1);
}
}
int main(){
int a[100]= {0,1,8,5,7,2,6,3,4,11,9};
HeapSort(a,10);
for(int i = 10;i>0;i--){
printf("%d ",a[i]);
}
return 0;
}
空间效率O（1），时间效率O（n*logN），不稳定。
归并排序
#include<bits/stdc++.h>
using namespace std;
void Merge(int a[],int low,int mid,int high){
int b[100];
for(int i= low;i<=high;i++) b[i]=a[i];
int i,j,k;
for(i=low,j=mid+1,k=i;i<=mid&&j<=high;){
if(b[i]<b[j]) {
a[k++]=b[i++];
}else {
a[k++]=b[j++];
}
}
while(i<=mid) a[k++]=b[i++];
while(j<=high) a[k++]=b[j++];
}
void MergeSort(int a[],int low,int high){
if(low<high){
int mid= (low+high)/2;
MergeSort(a,low,mid);
MergeSort(a,mid+1,high);
Merge(a,low,mid,high);
}
}
int main(){
int a[100]= {0,1,8,5,7,2,6,3,4,11,9};
MergeSort(a,0,10);
for(int i = 10;i>0;i--){
printf("%d ",a[i]);
}
return 0;
}
空间效率O（n），时间效率O（n*logN），稳定。
数学
素数
#include<bits/stdc++.h>
using namespace std;
bool isPrim(int n ){
if(n<=1) return false;
for(int i = 2;i<=sqrt(n);i++){
if(n%i==0) return false;
}
return true;
}
int main(){
int n = 13;
cout<<isPrim(n);
return 0;
}
最大公约数和最小公倍数
#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b){
return b==0?a:gcd(b,a%b);
}
int gbs(int a,int b){
return a*b/gcd(a,b);
}
int main(){
int a = 12,b = 8;
cout<<gcd(a,b)<<endl<<gbs(a,b);
return 0;
}
进一步可以打印素数表/使用素数筛（埃式筛）
质因子分解
#include<bits/stdc++.h>
using namespace std;
const int maxn = 100100;
struct factor{
int x;
int num;
}fac[10];
bool isPrim(int n){
if(n<=1) return false;
for(int i=2;i<=sqrt(n);i++){
if(n%i==0) return false;
}
return true;
}
int prims[maxn];
int cnt = 0;
void findPrim(){
for(int i = 1;i<maxn;i++){
if(isPrim(i)==true){
prims[cnt++] = i;
}
}
}
int main(){
findPrim();
int n;
int facNum = 0;
cin>>n;
if(n==1) printf("1=1");
else {
printf("%d=",n);
for(int i = 0;i<cnt;i++){
if(n%prims[i]==0){
fac[facNum].x=prims[i];
fac[facNum].num=0;
while(n%prims[i]==0){
n=n/prims[i];
fac[facNum].num++;
}
facNum++;
}
//已经除尽就跳出循环
if(n==1) break;
}
//最后余数不为1，则就是最后一个质因数
if(n!=1){
fac[facNum].x=n;
fac[facNum].num=1;
facNum++;
}
for(int i = 0;i<facNum;i++){
if(i>0) printf("*");
printf("%d",fac[i].x);
if(fac[i].num>1){
printf("^%d",fac[i].num);
}
}
}
return 0;
}
快速幂
#include<bits/stdc++.h>
using namespace std;
//求a的b次方，对m取余
long long binaryPow(long long a,long long b,long long m){
if(b==0) return 1;
if(b%2==1){
return binaryPow(a,b-1,m)%m;
}else{
long long temp = binaryPow(a,b/2,m);
return temp*temp%m;
}
}
int main(){
return 0;
}
STL
vector
#include<bits/stdc++.h>
using namespace std;
int main(){
vector<int>vi;
vi.push_back(1);
vi.push_back(2);
vi.push_back(3);
vi.push_back(4);
vi.push_back(5);
//访问方式
for(int i = 0;i<vi.size();i++) printf("%d ",vi[i]);
cout<<endl;
for(auto it = vi.begin();it!=vi.end();it++) printf("%d ",*it);
//各种操作
vi.push_back(6);
vi.pop_back();
cout<<vi.size();
vi.insert(vi.begin()+1,100);
vi.erase(vi.begin()+3);
vi.erase(vi.begin(),vi.begin()+1);
vi.clear();
return 0;
}
set
#include<bits/stdc++.h>
using namespace std;
int main(){
//自动排序和去重
set<int>si;
si.insert(10);
si.insert(10);
si.insert(1);
si.insert(9);
si.insert(6);
//访问方式
for(auto it=si.begin();it!=si.end();it++){
printf("%d ",*it);
}
//各种操作
si.insert(7);
printf("\n%d",*(si.find(9)));
si.erase(si.find(9));
si.erase(1);
si.erase(si.find(6),si.end());
cout<<si.size()<<endl;
si.clear();
return 0;
}
string
#include<bits/stdc++.h>
using namespace std;
int main(){
string str="adwe";
//访问方式
for(int i =0;i<str.size();i++){
cout<<str[i];
}
cout<<endl;
for(auto it=str.begin();it!=str.end();it++){
cout<<*it;
}
//各种操作
string a = " qqqq";
cout<<a+str<<endl;
bool temp = a>=str;
cout<<temp<<endl;
cout<<str.length()<<endl;
str.insert(3,"wd");
str.erase(str.begin()+2);
str.erase(str.begin()+2,str.end()-1);
str.substr(3,5);
str.clear();
str.find("ww");
str.replace(10,4,"w");
str.replace(str.begin(),str.begin()+1,"www");
return 0;
}
map
#include<bits/stdc++.h>
using namespace std;
int main(){
map<string,int>mp;
mp["w"]=1;
mp["e"]=2;
mp["r"]=3;
mp["q"]=4;
//访问方式
for(auto it=mp.begin();it!=mp.end();it++){
cout<< it->first<<" "<<it->second<<endl;
}
//各种操作
cout<< mp.find("w")->first<<" "<<mp.find("w")->second<<endl;
mp.erase(mp.find("w"));
mp.erase("w");
mp.erase(mp.begin(),mp.end());
mp.size();
mp.clear();
return 0;
}
queue
#include<bits/stdc++.h>
using namespace std;
int main(){
queue<int>q;
q.push(1);
q.push(3);
q.push(2);
q.push(4);
//访问方式
cout<<q.front()<<" "<<q.back()<<endl;
//各种操作
q.push(12);
cout<<q.front()<<" "<<q.back()<<endl;
q.pop();
cout<<q.empty()<<endl;
cout<<q.size()<<endl;
return 0;
}
priority_queue
#include<bits/stdc++.h>
using namespace std;
struct fruit{
string name;
int price;
friend bool operator <(fruit a,fruit b){
return a.price>b.price;
}
}f1,f2,f3,f4;
int main(){
priority_queue<fruit>pq;
f1.name="苹果";
f1.price=25;
f2.name="香蕉";
f2.price=12;
f3.name="桃子";
f3.price=19;
pq.push(f1);
pq.push(f2);
pq.push(f3);
//访问方式
cout << pq.top().price << " "<< pq.top().name <<endl;
//各种操作
f4.name="KK";
f4.price=13;
pq.push(f4);
cout << pq.top().price << " "<< pq.top().name <<endl;
pq.pop();
pq.empty();
pq.size();
return 0;
}
stack
#include<bits/stdc++.h>
using namespace std;
int main(){
stack<int>si;
si.push(1);
si.push(9);
si.push(6);
si.push(3);
//访问方式
cout<<si.top()<<endl;
//各种操作
si.push(20);
cout<<si.top()<<endl;
si.pop();
si.empty();
si.size();
return 0;
}
algorithm
#include<bits/stdc++.h>
using namespace std;
bool cmp (int a,int b){
return a>b;
}
int main(){
int a=8,b = -10;
cout<<max(a,b)<<" "<<min(a,b)<<" "<<abs(b)<<endl;
swap(a,b);
//对于数组，vector，string都可以进行排序
int q[10]={4,1,2,6};
reverse(q,q+4);
for(int i =0;i<4;i++) printf("%d ",q[i]);
cout<<endl;
//全排列，按从小到大顺序
int y[3]={1,2,3};
do{
printf("%d %d %d\n",y[0],y[1],y[2]);
}while(next_permutation(y,y+3));
//填充数组
int dis[5][5];
fill(dis[0],dis[0]+5*5,1);
for(int i = 0;i<5;i++){
for(int j = 0;j<5;j++){
printf("%d ",dis[i][j]);
}
printf("\n");
}
//sort排序
int p[10]={4,1,2,6};
sort(p,p+4,cmp);
for(int i =0;i<4;i++) printf("%d ",p[i]);
return 0;
}
树相关
二叉树（增删改查遍历，多种序列遍历求原树）
#include<bits/stdc++.h>
using namespace std;
//结构定义
struct node{
int data;
node* left;
node* right;
};
//新建结点
node* newNode(int v){
node* root = new node;
root->data=v;
root->left=root->right=NULL;
return root;
}
//修改/查找
void searchNode(node* root,int x,int v){
if(root==NULL) return;
if(root->data==x){
root->data= v;
}
searchNode(root->left,x,v);
searchNode(root->right,x,v);
}
//插入，需要&改变原root
void insertNode(node* &root,int x){
if(root==NULL) {
root=newNode(x);
return;
}
if(root->data>x){
insertNode(root->left,x);
}else insertNode(root->right,x);
}
//建树
node* creatTree(int data[],int n){
node* root=NULL;
for(int i = 0;i<n;i++){
insertNode(root,data[i]);
}
return root;
}
//先序遍历
void preOrder(node* root){
if(root==NULL){
return ;
}
printf("%d ",root->data);
preOrder(root->left);
preOrder(root->right);
}
//中序遍历
void inOrder(node* root){
if(root==NULL){
return ;
}
inOrder(root->left);
printf("%d ",root->data);
inOrder(root->right);
}
//后序遍历
void postOrder(node* root){
if(root==NULL){
return ;
}
postOrder(root->left);
postOrder(root->right);
printf("%d ",root->data);
}
//层序遍历
void traversal(node * root)
{
queue<node*>q;
q.push(root);
while(q.empty()==false){
node * temp =q.front();
q.pop();
printf("%d ",temp->data);
if(temp->left!=NULL) q.push(temp->left);
if(temp->right!=NULL) q.push(temp->right);
}
}
//中序和任意序遍历求原序列，其他同理
//举例：中序后序求层序遍历
int n=7;
int postorder[7]={2,3,1,5,7,6,4};
int inorder[7]={1,2,3,4,5,6,7};
node* create(int postleft,int postright,int inleft,int inright){
if(postleft>postright) return NULL;
node* root = new node;
root->data=postorder[postright];
int rootPos;
for(int i = inleft;i<=inright;i++){
if(inorder[i]==postorder[postright]){
rootPos=i;
}
}
int leftNum = rootPos-inleft;
root->left=create(postleft,postleft+leftNum-1,inleft,rootPos-1);
root->right=create(postleft+leftNum,postright-1,rootPos+1,inright);
}
int main(){
int data[10]={4,1,0,3,10,5,7,2,9,6};
reverse(data,data+10);
node* root = creatTree(data,10);
preOrder(root);
cout<<endl;
inOrder(root);
cout<<endl;
postOrder(root);
cout<<endl;
traversal(root);
//得到原树之后求层序遍历
cout<<endl;
node* root2 = create(0,6,0,6);
traversal(root2);
return 0;
}
树
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
//结构定义
struct node{
int data;
vector<int> child;
}Node[maxn];
//先根遍历
void preOrder(int root){
printf("%d ",Node[root].data);
for(int i = 0;i<Node[root].child.size();i++){
preOrder(Node[root].child[i]);
}
}
//后根遍历
void postOrder(int root){
for(int i = 0;i<Node[root].child.size();i++){
postOrder(Node[root].child[i]);
}
printf("%d ",Node[root].data);
}
//层次遍历
void layerOrder(int root){
queue<int>q;
q.push(root);
while(!q.empty()){
int top = q.front();
q.pop();
printf("%d ",Node[top].data);
for(int i = 0;i<Node[top].child.size();i++){
q.push(Node[top].child[i]);
}
}
}
//例题PAT A1053
int n,m,s;
int weight[maxn];
int cnt = 0;
vector<int>path;
vector<int>paths[maxn];
void DFS(int id,int sum){
if(sum>s) return;
if(sum==s){
if(Node[id].child.size()!=0) return;
paths[cnt++]=path;
return;
}
for(int i=0;i<Node[id].child.size();i++){
path.push_back(Node[id].child[i]);
DFS(Node[id].child[i],sum+weight[Node[id].child[i]]);
path.pop_back();
}
}
bool cmp(int a,int b){
return weight[a]>weight[b];
}
int main(){
scanf("%d %d %d",&n,&m,&s);
for(int i = 0;i<n;i++) scanf("%d",&weight[i]);
for(int i = 0;i<m;i++){
int id,num;
scanf("%d %d",&id,&num);
for(int j=0;j<num;j++){
int temp;
scanf("%d",&temp);
Node[id].child.push_back(temp);
}
//直接这里进行排序，顺序dfs之后就是有序从大到小的序列
sort(Node[id].child.begin(),Node[id].child.end(),cmp);
}
path.push_back(0);
DFS(0,weight[0]);
for(int i = 0;i<cnt;i++){
vector<int>temp = paths[i];
for(int j = 0;j<temp.size();j++){
printf("%d",weight[temp[j]]);
if(j!=temp.size()-1) printf(" ");
}
printf("\n");
}
return 0;
}
二叉搜索树BST
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
//结构定义
struct node{
int data;
node* left;
node* right;
};
//新建结点
node* newNode(int x){
node * root=new node;
root->data=x;
root->left=root->right=NULL;
return root;
}
//插入结点
void insertNode(node* &root,int x){
if(root==NULL){
root=newNode(x);
return;
}
if(root->data>x){
insertNode(root->left,x);
}else insertNode(root->right,x);
}
//建树
node* create(int data[],int n){
node *root=NULL;
for(int i =0;i<n;i++){
insertNode(root,data[i]);
}
return root;
}
//找前驱
node* findMax(node* root){
while(root->right!=NULL){
root=root->right;
}
return root;
}
//找后继
node* findMin(node* root){
while(root->left!=NULL){
root=root->left;
}
return root;
}
//删除结点
void deleteNode(node* &root,int x){
if(root==NULL) return;
if(root->data==x){
if(root->left==NULL&&root->right==NULL) root=NULL;
else if(root->left!=NULL){
node* pre=findMax(root->left);
root->data = pre->data;
deleteNode(root->left,pre->data);
}else{
node* next = findMin(root->right);
root->data=next->data;
deleteNode(root->right,next->data);
}
}else if(root->data>x){
deleteNode(root->left,x);
}else deleteNode(root->right,x);
}
//先序遍历
void preOrder(node* root){
if(root==NULL) return;
printf("%d ",root->data);
preOrder(root->left);
preOrder(root->right);
}
//中序遍历
void inOrder(node* root){
if(root==NULL) return;
inOrder(root->left);
printf("%d ",root->data);
inOrder(root->right);
}
//后序遍历
void postOrder(node* root){
if(root==NULL) return;
postOrder(root->left);
postOrder(root->right);
printf("%d ",root->data);
}
int main(){
int data[10]={5,3,7,4,2,8,6};
node* root=create(data,7);
preOrder(root);
cout<<endl;
deleteNode(root,5);
preOrder(root);
return 0;
}
平衡二叉树AVL
#include<bits/stdc++.h>
using namespace std;
//结构定义
struct node{
int data;
int height;
node* left;
node* right;
};
//新建结点
node* newNode(int x){
node* root = new node;
root->data=x;
root->height=1;
root->left=root->right=NULL;
return root;
}
//求结点高度
int getHeight(node* root){
if(root==NULL) return 0;
return root->height;
}
//求结点平衡因子
int getBalanceFactor(node *root){
return getHeight(root->left)-getHeight(root->right);
}
//更新结点高度
void updateHeight(node *root){
root->height= max(getHeight(root->left),getHeight(root->right))+1;
}
//左旋
void L(node* &root){
node* temp = root->right;
root->right=temp->left;
temp->left=root;
updateHeight(root);
updateHeight(temp);
root=temp;
}
//右旋
void R(node* &root){
node* temp = root->left;
root->left=temp->right;
temp->right=root;
updateHeight(root);
updateHeight(temp);
root=temp;
}
//插入结点
void insertNode(node* &root,int x){
if(root==NULL){
root=newNode(x);
return;
}
if(root->data>x){
insertNode(root->left,x);
updateHeight(root);
if(getBalanceFactor(root)==2){
if(getBalanceFactor(root->left)==1){
R(root);
}else if(getBalanceFactor(root->left)==-1){
L(root->left);
R(root);
}
}
}else{
insertNode(root->right,x);
updateHeight(root);
if(getBalanceFactor(root)==-2){
if(getBalanceFactor(root->right)==-1){
L(root);
}else if(getBalanceFactor(root->right)==1){
R(root->right);
L(root);
}
}
}
}
//建树
node* create(int data[],int n){
node* root=NULL;
for(int i=0;i<n;i++){
insertNode(root,data[i]);
}
return root;
}
//前序遍历
void preOrder(node* root){
if(root==NULL) return;
printf("%d ",root->data);
preOrder(root->left);
preOrder(root->right);
}
int main(){
int data[10]={5,3,7,4,2,8,6};
node* root=create(data,7);
preOrder(root);
return 0;
}
并查集
#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;
int father[maxn];
int n;
//初始化
void init(){
for(int i = 1;i<=n;i++){
father[i]=i;
}
}
//找到所在集合根节点
int findFather(int x){
while(x!=father[x]){
x=father[x];
}
return x;
}
//找到所在集合根节点，使用路径压缩O(1)
int findFather2(int x){
int a=x;
while(x!=father[x]){
x=father[x];
}
while(a!=father[a]){
int z=a;
a=father[a];
father[z]=x;
}
return x;
}
//合并两个集合
void unionAll(int a,int b){
int fa=findFather(a);
int fb=findFather(b);
if(fa!=fb){
father[fa]=fb;
}
}
int main(){
return 0;
}
堆
#include<bits/stdc++.h>
using namespace std;
//堆常用来实现优先队列
const int maxn = 1010;
int heap[maxn];
int n = 10;
//向下调整
void adjust(int low,int high){
int i=low,j=i*2;
while(j<=high){
if(j+1<=high&&heap[j+1]>heap[j]){
j=j+1;
}
if(heap[j]>heap[i]){
swap(heap[j],heap[i]);
i=j;
j=2*i;
}else{
break;
}
}
}
//建堆，从n/2开始向1调整
void createHeap(){
for(int i=n/2;i>=1;i--){
adjust(i,n);
}
}
void deleteTop(){
heap[1]=heap[n];
n--;
adjust(1,n);
}
//添加结点时向上调整
void upAdjust(int low,int high){
int i=high,j=i/2;
while(j>=low){
if(heap[j]<heap[i]){
swap(heap[j],heap[i]);
i=j;
j=i/2;
}else break;
}
}
//添加结点
void insert(int x){
heap[n++]=x;
upAdjust(1,n);
}
//堆排序，堆顶与最后一个元素交换，再从上往下调整堆
void heapSort(){
createHeap();
for(int i=n;i>1;i--){
swap(heap[i],heap[1]);
adjust(1,i-1);
}
}
int main(){
return 0;
}
图相关
图遍历DFS
#include<bits/stdc++.h>
using namespace std;
//最大顶点数
const int maxn = 1000;
//设置为最大数
const int INF = 1000000000;
//邻接矩阵
int n,G[maxn][maxn]；
bool vis[maxn]={false};
void DFS(int u,int depth)
{
vis[u]=true;
for(int i=0;i<n;i++){
if(vis[i]==false && G[u][i]!=INF){
DFS(i,depth+1);
}
}
}
void DFSG()
{
for(int i=0;i<n;i++){
if(vis[i]==false){
DFS(i,1);
}
}
}
//邻接表实现
vector<int>adj[maxn];
void DFS2(int u,int depth){
vis[u]=true;
for(int i=0;i<adj[u].size();i++){
int temp = adj[u][i];
if(vis[temp]==false && G[u][temp]!=INF){
DFS(temp,depth+1);
}
}
}
void DFSG2()
{
for(int i=0;i<n;i++){
if(vis[i]==false){
DFS(i,1);
}
}
}
int main(){
return 0;
}
PAT A1034例题
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2020;
const int INF=1000000000;
int n,k,id=0;
int G[maxn][maxn]={0},weight[maxn]={0};
bool vis[maxn]= {false};
map<string,int>sti;
map<int,string>its;
map<string,int>GANG;
int stringtoint(string x)
{
if(sti.find(x)!=sti.end())
{
return sti[x];
}else
{
sti[x] = id;
its[id] = x;
return id++;
}
}
void DFS(int index,int &totaltime,int &membernum,int &head)
{
membernum++;
vis[index]=true;
if(weight[index]>weight[head]) head=index;
for(int i=0; i<id; i++)
{
if(G[index][i]>0)
{
totaltime+=G[index][i];
G[index][i]=G[i][index]=0;
if(vis[i]==false) DFS(i,totaltime,membernum,head);
}
}
}
void DFSG()
{
for(int i=0; i<id; i++)
{
if(vis[i]==false)
{
int totaltime=0,membernum=0,head=i;
DFS(i,totaltime,membernum,head);
if(membernum>2&&totaltime>k)
{
GANG[its[head]] = membernum;
}
}
}
}
int main(int argc, const char * argv[])
{
string a,b;
int time;
cin>>n>>k;
for(int i=0; i<n; i++)
{
cin>>a>>b>>time;
int persona = stringtoint(a);
int personb = stringtoint(b);
G[persona][personb]+=time;
G[personb][persona]+=time;
weight[persona]+=time;
weight[personb]+=time;
}
DFSG();
printf("%d\n",GANG.size());
for(auto it = GANG.begin(); it != GANG.end(); it++)
cout << it->first << " " << it->second << endl;
return 0;
}
图遍历BFS
#include<bits/stdc++.h>
using namespace std;
//最大顶点数
const int maxn = 1000;
//设置为最大数
const int INF = 1000000000;
//邻接矩阵
int n,G[maxn][maxn]；
bool vis[maxn]={false};
void BFS(int u){
queue<int>q;
q.push(u);
vis[u]=true;
while(!q.empty()){
int top = q.front();
q.pop();
for(int i=0;i<n;i++){
if(vis[i]==false && G[top][i]!=INF){
q.push(i);
vis[i]=true;
}
}
}
}
void BFSG(){
for(int i=0;i<n;i++){
if(vis[i]==false){
BFS(i);
}
}
}
//邻接表实现
vector<int>adj[maxn];
void BFS2(int u){
queue<int>q;
q.push(u);
vis[u]=true;
while(!q.empty()){
int top = q.front();
q.pop();
for(int i=0;i<adj[top].size();i++){
int temp = adj[top][i];
if(vis[temp]==false){
q.push(temp);
vis[temp]=true;
}
}
}
}
void BFSG2(){
for(int i=0;i<n;i++){
if(vis[i]==false){
BFS(i);
}
}
}
int main(){
return 0;
}
PAT A1076
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2020;
struct Node
{
int id;
int layer;
};
vector<Node>adj[maxn];
bool vis[maxn] = {false};
int BFS(int st,int maxl)
{
int cnt=0;
queue<Node>q;
Node start;
start.id=st;
start.layer = 0;
q.push(start);
vis[start.id]=true;
while(!q.empty())
{
Node top = q.front();
q.pop();
int u=top.id;
for(int i=0;i<adj[u].size();i++)
{
Node next = adj[u][i];
next.layer = top.layer+1;
if(vis[next.id]==false && next.layer<=maxl)
{
q.push(next);
vis[next.id] = true;
cnt++;
}
}
}
return cnt;
}
int main()
{
Node user;
int n, L, numFollow, idFollow;
cin >> n >> L;//结点个数，层数上限
for(int i = 1; i <= n; i++){
user.id = i; //用户编号为i
cin >> numFollow;//i号用户关注的人数
for(int j = 0; j < numFollow; j++){
cin >> idFollow;//i号用户关注的用户编号
adj[idFollow].push_back(user);//边idFollow->i
}
}
int numQuery, s;
cin >> numQuery;//查询个数
for(int i = 0; i < numQuery; i++){
memset(vis, false, sizeof(vis));
cin >> s;//起始结点编号
int numForward = BFS(s, L);
cout << numForward << endl;
}
return 0;
}
最短路径
dijkstra
#include<bits/stdc++.h>
using namespace std;
//最大顶点数
const int maxn = 1000;
//设置为最大数
const int INF = 1000000000;
//邻接矩阵
int n,G[maxn][maxn];
int d[maxn];
bool vis[maxn];
void dijkstra(int s){
fill(vis,vis+maxn,false);
fill(d,d+maxn,INF);
d[s]=0;
for(int i = 0;i<n;i++){
int u=-1,MIN=INF;
for(int j = 0;j<n;j++){
if(vis[j]==false && d[j]<MIN){
u=j;
MIN=d[j];
}
}
if(u==-1) return;
vis[u]=true;
for(int v=0;v<n;v++){
if(vis[v]==false &&G[u][v]!=INF){
if(d[u]+G[u][v]<d[v]){
d[v]=d[u]+G[u][v];
}
}
}
}
}
//邻接表实现
struct node{
int v,dis;
};
vector<node>adj[maxn];
void dijkstra2(int s){
fill(vis,vis+maxn,false);
fill(d,d+maxn,INF);
d[s]=0;
for(int i = 0;i<n;i++){
int u = -1,MIN=INF;
for(int j=0;j<n;j++){
if(vis[j]==false &&d[j]<MIN){
MIN=d[j];
u=j;
}
}
if(u==-1) return;
vis[u]=true;
for(int i =0;i<adj[u].size();i++){
int v=adj[u][i].v;
if(vis[v]==false){
if(d[u]+adj[u][i].dis<d[v]){
d[v]=d[u]+adj[u][i].dis;
}
}
}
}
}
int main(){
int u,v,w;
int m,s;
scanf("%d%d%d",&n,&m,&s);
fill(G[0],G[0]+maxn*maxn,INF);
for(int i=0;i<m;i++){
scanf("%d%d%d",&u,&v,&w);
G[u][v]=w;
G[v][u]=w;
}
dijkstra(s);
for(int i=0;i<n;i++) printf("%d ",d[i]);
return 0;
}
例题PAT A1003（加入点权，路径数等第二衡量标准）
#include<bits/stdc++.h>
using namespace std;
//最大顶点数
const int maxn = 1000;
//设置为最大数
const int INF = 1000000000;
//邻接矩阵
int n,m,st,ed,G[maxn][maxn];
int d[maxn];
int w[maxn];
int num[maxn];
int weight[maxn];
bool vis[maxn];
void Dijkstra(int s)
{
fill(d,d+maxn,INF);
fill(w,w+maxn,0);
fill(num,num+maxn,0);
fill(vis,vis+maxn,false);
d[s]=0;
w[s]=weight[s];
num[s]=1;
for(int i=0;i<n;i++){
int u=-1,MIN=INF;
for(int j=0;j<n;j++){
if(vis[j]==false &&d[j]<MIN){
MIN=d[j];
u=j;
}
}
if(u==-1) return;
vis[u]=true;
for(int v=0;v<n;v++){
if(vis[v]==false&&G[u][v]!=INF){
if(d[u]+G[u][v]<d[v]){
d[v]=d[u]+G[u][v];
w[v]=w[u]+weight[v];
num[v]=num[u];
}else if(d[u]+G[u][v]==d[v]){
if(w[u]+weight[v]>w[v]){
w[v]=w[u]+weight[v];
}
num[v]+=num[u];
}
}
}
}
}
int main(){
scanf("%d%d%d%d",&n,&m,&st,&ed);
for(int i=0;i<n;i++) scanf("%d",&weight[i]);
fill(G[0],G[0]+maxn*maxn,INF);
for(int i=0;i<m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
G[a][b]=G[b][a]=c;
}
Dijkstra(st);
printf("%d %d",num[ed],w[ed]);
return 0;
}
Floyd
#include<bits/stdc++.h>
using namespace std;
//最大顶点数
const int maxn = 1000;
//设置为最大数
const int INF = 1000000000;
int n,m;
int dis[maxn][maxn];
void Floyd(){
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][k]+dis[k][j]<dis[i][j]){
dis[i][j]=dis[i][k]+dis[k][j];
}
}
}
}
}
int main(){
int u,v,w;
fill(dis[0],dis[0]+maxn*maxn,INF);
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d%d",&u,&v,&w);
dis[u][v]=w;
}
Floyd();
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
printf("%d ",dis[i][j]);
}
printf("\n");
}
return 0;
}
最小生成树
#include<bits/stdc++.h>
using namespace std;
//最大顶点数
const int maxn = 1000;
//设置为最大数
const int INF = 1000000000;
int n,G[maxn][maxn];
int d[maxn];//顶点到集合S最短距离
bool vis[maxn];
int Prim(){
fill(d,d+maxn,INF);
d[0]=0;
int ans=0;
for(int i=0;i<n;i++){
int u=-1,MIN=INF;
for(int j=0;j<n;j++){
if(vis[j]==false &&d[j]<MIN){
u=j;
MIN=d[j];
}
}
if(u==-1) return;
vis[u]=true;
ans+=d[u];
for(int v=0;v<n;v++){
if(vis[v]==false && G[u][v]!=INF&&G[u][v]<d[v]){
d[v]=G[u][v];
}
}
}
return ans;
}
int main(){
int u,v,w;
fill(G[0],G[0]+maxn*maxn,INF);
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d%d",&u,&v,&w);
G[u][v]=G[v][u]=w;
}
printf("%d\n",Prim());
return 0;
}
kruskal
#include<bits/stdc++.h>
using namespace std;
//最大顶点数
const int maxn = 110;
const int maxe= 10010;
//设置为最大数
const int INF = 1000000000;
struct edge{
int u,v;
int cost;
}E[maxe];
bool cmp(edge a,edge b){
return a.cost<b.cost;
}
int father[maxn];
int findFather(int x){
int a=x;
while(x!=father[x]){
x=father[x];
}
while(a!=father[a]){
int z=a;
a=father[a];
father[z]=x;
}
return x;
}
int kruskal(int n,int m){
int ans=0,edgeNum=0;
for(int i=0;i<n;i++){
father[i]=i;
}
sort(E,E+m,cmp);
for(int i=0;i<m;i++){
int fu=findFather(E[i].u);
int fv=findFather(E[i].v);
if(fu!=fv){
father[fu]=fv;
ans+=E[i].cost;
edgeNum++;
if(edgeNum==n-1) break;
}
}
if(edgeNum!=n-1) return -1;
else return ans;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].cost);
}
printf("%d\n",kruskal(n,m));
return 0;
}
有向无环图
#include<bits/stdc++.h>
using namespace std;
//最大顶点数
const int maxn = 1010;
vector<int>G[maxn];
int n,m,inDegree[maxn];
bool topologicalSort(){
int num=0;
queue<int>q;
for(int i=0;i<n;i++){
if(inDegree[i]==0) q.push(i);
}
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
inDegree[v]--;
if(inDegree[v]==0){
q.push(v);
}
}
G[u].clear();
num++;
}
if(num==n) return true;
else return false;
}
int main(){
return 0;
}
