Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <fstream>
- std::ifstream file("text.txt");
- void DFS(int st,int**graph,bool*visited,int point)
- {
- int r;
- //std::cout<<st+1<<" ";
- visited[st]=true;
- for (r=0; r < point; r++)
- if ((graph[st][r]!=0) && (!visited[r]))
- DFS(r,graph,visited,point);
- }
- bool isConnected(int **graph,bool*visited,int point)
- {
- for (int i =0; i < point; i++)
- {
- visited[i]=false;
- }
- DFS(0, graph,visited,point);
- for (int i =0; i < point; i++)
- {
- if (!visited[i])
- return false;
- }
- return true;
- }
- bool prov_del(int **mas_smez,int **maas_isx,int point,bool*visited,int del_reb)
- { if(!isConnected(mas_smez,visited,point))
- return !isConnected(mas_smez,visited,point);
- bool a;
- int**mas_smez1;
- mas_smez1=new int*[point] ;
- for (int i = 0; i < point; ++i)
- {
- mas_smez1[i]=new int[point];
- }
- for (int i = 0; i < point; ++i)
- {
- for (int j = 0; j < point; ++j)
- {
- mas_smez1[i][j]=mas_smez[i][j];
- }
- }
- if(del_reb>1)
- {
- for (int i = 0; i < point ; ++i)
- {
- for (int j = 0; j < point; ++j)
- {
- if(mas_smez1[i][j]==1)
- {
- mas_smez1[i][j]=0;
- mas_smez1[j][i]=0;
- maas_isx[i][j]=0;
- maas_isx[j][i]=0;
- if(prov_del(mas_smez1,maas_isx,point,visited,del_reb))
- {
- a=prov_del(mas_smez1,maas_isx,point,visited,del_reb);
- for (int i = 0; i < point; ++i)
- {
- delete []mas_smez1[i];
- }
- delete []mas_smez1;
- return a;
- }
- maas_isx[i][j]=1;
- maas_isx[j][i]=1;
- mas_smez1[i][j]=1;
- mas_smez1[j][i]=1;
- }
- }
- }
- }
- else
- {
- for (int i = 0; i < point ; ++i)
- {
- for (int j = 0; j < point; ++j)
- {
- if(mas_smez1[i][j]==1)
- {
- mas_smez1[i][j]=0;
- mas_smez1[j][i]=0;
- maas_isx[i][j]=0;
- maas_isx[j][i]=0;
- if(!isConnected(mas_smez1,visited,point))
- {
- a = !isConnected(mas_smez1,visited,point);
- for (int i = 0; i < point; ++i)
- {
- delete []mas_smez1[i];
- }
- delete []mas_smez1;
- return a;
- }
- maas_isx[i][j]=1;
- maas_isx[j][i]=1;
- mas_smez1[i][j]=1;
- mas_smez1[j][i]=1;
- }
- }
- }
- return false;
- }
- }
- int main(int argc, char const *argv[])
- {
- int **mas_smez;
- int **maas_isx;
- int point;
- bool *visited;
- int a=-1;
- file>>point;
- visited=new bool[point] ;
- mas_smez=new int*[point] ;
- for (int i = 0; i < point; ++i)
- {
- mas_smez[i]=new int[point];
- }
- maas_isx=new int*[point] ;
- for (int i = 0; i < point; ++i)
- {
- maas_isx[i]=new int[point];
- }
- for (int i = 0; i < point; ++i)
- {
- for (int j = 0; j < point; ++j)
- {
- file>>mas_smez[i][j];
- }
- }
- for (int i = 0; i < point; ++i)
- {
- for (int j = 0; j < point; ++j)
- { maas_isx[i][j]=mas_smez[i][j];
- std::cout<<mas_smez[i][j]<<" ";
- }
- std::cout<<std::endl;
- }
- for (int i = 1; i < point; ++i)
- {
- if(prov_del(mas_smez,maas_isx,point,visited,i))
- {
- a=i;
- break;
- }
- }
- std::cout<<a<<std::endl;
- for (int i = 0; i < point; ++i)
- {
- for (int j = 0; j < point; ++j)
- {
- std::cout<<maas_isx[i][j]<<" ";
- }
- std::cout<<std::endl;
- }
- for (int i = 0; i < point; ++i)
- {
- delete []mas_smez[i];
- }
- delete []mas_smez;
- for (int i = 0; i < point; ++i)
- {
- delete []maas_isx[i];
- }
- delete []maas_isx;
- delete []visited;
- file.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement