首页 > ACM题库 > HDU-杭电 > HDU 3849-By Recognizing These Guys, We Find Social Networks Useful-DFS-[解题报告]HOJ
2015
04-13

HDU 3849-By Recognizing These Guys, We Find Social Networks Useful-DFS-[解题报告]HOJ

By Recognizing These Guys, We Find Social Networks Useful

问题描述 :

Social Network is popular these days.The Network helps us know about those guys who we are following intensely and makes us keep up our pace with the trend of modern times.
But how?
By what method can we know the infomation we wanna?In some websites,maybe Renren,based on social network,we mostly get the infomation by some relations with those "popular leaders".It seems that they know every lately news and are always online.They are alway publishing breaking news and by our relations with them we are informed of "almost everything".
(Aha,"almost everything",what an impulsive society!)
Now,it’s time to know what our problem is.We want to know which are the key relations make us related with other ones in the social network.
Well,what is the so-called key relation?
It means if the relation is cancelled or does not exist anymore,we will permanently lose the relations with some guys in the social network.Apparently,we don’t wanna lose relations with those guys.We must know which are these key relations so that we can maintain these relations better.
We will give you a relation description map and you should find the key relations in it.
We all know that the relation bewteen two guys is mutual,because this relation description map doesn’t describe the relations in twitter or google+.For example,in the situation of this problem,if I know you,you know me,too.

输入:

The input is a relation description map.
In the first line,an integer t,represents the number of cases(t <= 5).
In the second line,an integer n,represents the number of guys(1 <= n <= 10000) and an integer m,represents the number of relations between those guys(0 <= m <= 100000).
From the second to the (m + 1)the line,in each line,there are two strings A and B(1 <= length[a],length[b] <= 15,assuming that only lowercase letters exist).
We guanrantee that in the relation description map,no one has relations with himself(herself),and there won’t be identical relations(namely,if "aaa bbb" has already exists in one line,in the following lines,there won’t be any more "aaa bbb" or "bbb aaa").
We won’t guarantee that all these guys have relations with each other(no matter directly or indirectly),so of course,maybe there are no key relations in the relation description map.

输出:

The input is a relation description map.
In the first line,an integer t,represents the number of cases(t <= 5).
In the second line,an integer n,represents the number of guys(1 <= n <= 10000) and an integer m,represents the number of relations between those guys(0 <= m <= 100000).
From the second to the (m + 1)the line,in each line,there are two strings A and B(1 <= length[a],length[b] <= 15,assuming that only lowercase letters exist).
We guanrantee that in the relation description map,no one has relations with himself(herself),and there won’t be identical relations(namely,if "aaa bbb" has already exists in one line,in the following lines,there won’t be any more "aaa bbb" or "bbb aaa").
We won’t guarantee that all these guys have relations with each other(no matter directly or indirectly),so of course,maybe there are no key relations in the relation description map.

样例输入:

1
4 4
saerdna aswmtjdsj
aswmtjdsj mabodx
mabodx biribiri
aswmtjdsj biribiri

样例输出:

1
saerdna aswmtjdsj

注意字符的处理 还有特殊情况,如果原图不连通,输出0

/******************************
无向图
******************************/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
#include <string>
#include <algorithm>
#define INF 0x3f3f3f3f
#define BUG printf("here!\n")
using namespace std;

const int MAXN=300000;
const int MAXM=600000;
struct node
{
    int u,v;
};
node edge[MAXM];
int first[MAXN],next[MAXM],cc;
int dfn[MAXN],low[MAXN],belong[MAXN];
int ti,id,top;
int stack[MAXN];
int arc[MAXM];  //桥边的集合,
int arcid;       //从0开始
inline void add_edge(int u,int v)
{
    edge[cc].u=u;
    edge[cc].v=v;
    next[cc]=first[u];
    first[u]=cc;
    cc++;
}
void tardfs(int u,int p)
{
    dfn[u]=low[u]=ti++;
    stack[top++]=u;
    int i;
    int ff=1;
    for(i=first[u];i!=-1;i=next[i])
    {
        int v=edge[i].v;
        if(v==p&&ff)       //处理重边
        {
            ff=0;
            continue;
        }
        if(dfn[v]==-1)
        {
            tardfs(v,u);
            if(low[u]>low[v])
                low[u]=low[v];
            else if(low[v]>dfn[u])
            {
                arc[arcid]=i;   //存的桥是原图中的标号
                arcid++;
                id++;
                for(stack[top]=-1;stack[top]!=v;)
                {
                    top--;
                    belong[stack[top]]=id;
                }
            }
        }
        else if(low[u]>dfn[v])
            low[u]=dfn[v];
    }
}
int tarjan(int n)
{
    ti=1;               //时间标号从1开始
    id=0;               //belong标号从1开始
    top=0;              //栈的标号从0开始,指向下一个位置
    arcid=0;            //桥边的标号从0开始;
    memset(dfn,-1,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(belong,0,sizeof(belong));
    tardfs(1,-1);

    return id;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(first,-1,sizeof(first));
        memset(next,-1,sizeof(next));
        cc=0;
        int n,m;
        scanf("%d%d",&n,&m);
        map<string,int> mp1;
        map<int,string> mp2;
        int cnt=1;
        int i;
        char str1[150],str2[150];
        for(i=0;i<m;i++)
        {
            scanf("%s%s",str1,str2);
            if(mp1[str1]==0)
            {
                mp1[str1]=cnt;
                mp2[cnt]=str1;
                cnt++;
            }
            if(mp1[str2]==0)
            {
                mp1[str2]=cnt;
                mp2[cnt]=str2;
                cnt++;
            }
            int u=mp1[str1];
            int v=mp1[str2];
            add_edge(u,v);
            add_edge(v,u);
        }
        tarjan(n);
        int flag=0;
        for(i=1;i<=n;i++)
        {
            if(dfn[i]==-1)
                flag=1;
        }
        if(flag)
        {
            printf("0\n");
            continue;
        }
        sort(arc,arc+arcid);
        //printf("%d\n",cnt);
        printf("%d\n",arcid);
        for(i=0;i<arcid;i++)
        {
            int x=arc[i];
            x=min(x,x^1);
            printf("%s %s\n",mp2[edge[x].u].c_str(),mp2[edge[x].v].c_str());
        }
    }

    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/juststeps/article/details/9357695


, ,
  1. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false