Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <vector>
- #include <map>
- #include <queue>
- using namespace std;
- int main(){
- int n,e,u,v,i,j;
- printf("Input Node and Vertex size: ");
- scanf("%d %d",&n,&e);
- printf("Input the Vertices:\n");
- vector<int> list[n+5];
- map<int,int>matrix[n+5];
- for (i=0; i<e; i++){
- scanf("%d %d",&u,&v);
- list[u].push_back(v);
- list[v].push_back(u);
- matrix[u][v]=1;
- matrix[v][u]=1;
- }
- printf("\nAdjusency List.\n");
- for (i=0; i<=n; i++){
- if (!list[i].empty()){
- printf("%d=",i);
- for (j=0; j<list[i].size();j++)
- printf(" %d",list[i][j]);
- puts("");
- }
- }
- printf("\nAdjusency Matrix.\n");
- for (i=0; i<=n; i++){
- for (j=0; j<=n;j++)
- printf(" %d",matrix[i][j]);
- puts("");
- }
- printf("\nBFS from %d.\n",u);
- int vis[n+2];
- memset(vis,0,sizeof vis);
- queue<int>q;
- q.push(u); ///Start from u.
- vis[u]=1;
- while (!q.empty()){
- u=q.front(); q.pop();
- printf("%d ",u);
- int c=(vis[u]==1 ? 2:1); ///for Bicoloring
- for (i=0; i<list[u].size(); i++){
- v=list[u][i];
- if (!vis[v]){
- vis[v]=c;
- q.push(v);
- }
- /*else if (vis[y]!=c){
- printf("Impossible bicoloring.\n");
- break;
- }*/
- }
- } return !puts("");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement