30/09/2018, 20:23

Hỏi về cách sử dụng bảng băm

Em có bài tập như sau:
Đơn đồ thị hữu hướng (simple complete dirgraph) đầy đủ là một đồ thị mà trong đó giữa hai đỉnh u, v bất kỳ sẽ được nối với nhau bởi một duy nhất một cặp cạnh (một cạnh có hướng từ u sang v và cạnh còn lại từ v sang u).
Cho một đồ thị hãy kiểm tra xem đồ thị đó có đầy đủ hay không

INPUT:
Dòng đầu tiên chứa số e, đây là độ dài của input
e dòng tiếp theo, mỗi dòng chứa 02 chuỗi u và i (cách nhau bởi khoảng trắng), thể hiện việc có một cạnh nối từ đỉnh u sang đỉnh i trong đồ thị. Do đây là đơn đồ thị nên nếu như có nhiều dòng cùng chứa hai chuỗi u, i giống nhau vẫn chỉ xem như có một cạnh nối từ u sang i.

OUTPUT:
Xuất ra màn hình chuỗi TRUE nếu đồ thị là đầy đủ. Nếu không xuất ra chuỗi FALSE

VD:

Vì đồ thị có tên đỉnh nên em định dùng danh sách kề để thể hiện , e khai báo thế nào có ổn không , ai giúp e cách xuất với ạ .

    string u, v;
int n;
cin >> n;
map<string, set<string>>A;
map<string, set<string>>::iterator it; 
for (int i = 0; i < n; i++)
{	
	
	cin.ignore();
	getline(cin, u);
	getline(cin, v);
	A[u].insert(v);
}

for (it = A.begin(); it != A.end(); it++)
{
	...
}

Khương Trương viết 22:38 ngày 30/09/2018

nếu băm thì băm từ chuỗi ra số rồi đưa nó vào mảng con.

Đông viết 22:39 ngày 30/09/2018

Bài này mình làm được rồi , cảm ơn nha . Bây giờ mình muốn hỏi là bây giờ muốn lưu thêm độ dài của cạnh thì mình cấu trúc dữ liệu như vậy có được ko !?
typedef struct Data
{
string temp;
int dodai;
}

sau đó khai báo: map< string , set < Data > > mymap;
bây giờ vấn đề của mình là làm sao dùng hàm insert trong stl map @@ , lúc đầu chỉ có
map < string , set < string > > thì làm đc , giờ thì ko hiểu làm sao để chèn , có thể giúp giùm mình đc k

Gió viết 22:30 ngày 30/09/2018

muốn dùng dc set thì phải có toán tử so sánh cho nó

//so sanh theo độ dài
bool operator<(const Data & a, const Data & b){
    return a.dodai<b.dodai;
}

Còn không bạn có thể dùng pair<int,string> như là Data

Đông viết 22:38 ngày 30/09/2018

oh ! tks sư huynh nhiều lắm , vật lộn với mấy bài đồ thị này quá @@ tìm tài liệu trên google nó lung tung quá nên ko hiểu !! tiếng anh thì phập phù ko biết tìm sao nữa !!

Đông viết 22:39 ngày 30/09/2018

typedef string Node;
typedef pair<Node, int> Data;
typedef map<Node, set<Data> > Graph;
Graph g;
void addEgde(Node u, Data v)
{
	g[u].insert(v);
}
int main()
{
	int n, x;
	Node u;
	Data v;
	cin >> e;
	for (int i = 0; i < n; i++)
	{
		cin >> u;
		cin >> v.first;
		cin >> v.second;
		addEgde(u, v);
	}
	for (auto n : g)
	{
		cout << n.first << " - ";
	}
	system("pause");
	return 0;
}

e làm như v thì lưu đc , nhưng làm sao lấy ra đc phần tử của lớp pair vậy a !! lấy đc phần tử đầu là n.first nhưng n.second ở sau ( pair< string,int > ) ko bik làm sao xuất ra đc

Gió viết 22:30 ngày 30/09/2018

n.second là kiểu set bạn xuất nó như bình thường thôi

for(auto data: n.second){
   cout<<data.first<<": "<<data.second<<endl;
}

Đông viết 22:30 ngày 30/09/2018

Hi , tks a nha lúc học môn CTDL toàn code tay thôi , mà cũng ko code tới map,set nên chả biết gì , chuyển qua môn AI thầy kêu tìm hiểu xài hàm trong STL nên có gì thắc mắc e lên hỏi a nha , a có hay onl facebook ko có thể cho e add friend để có gì trao đổi, giúp e đc ko ak ^^

muadong viết 22:38 ngày 30/09/2018

Bài bạn post ở trên khá hay hồi h chưa đụng nhiều đến cái thư viện chuẩn không biết bài trên nếu dùng theo mảng băm thì làm như thế nào để cùng học hỏi thk!

Đông viết 22:30 ngày 30/09/2018

Mình làm theo kiểu map < string , set < string> > để lưu danh sách kề !

Đông viết 22:24 ngày 30/09/2018

A ơi , bây giờ muốn tính độ dài đường đi cho trước thì tìm như thế nào ạ, VD : F L F . nếu có đường đi thì xuất ra độ dài FL + LF . e vướng chỗ tìm kiếm trong set . để lưu mảng đường đi kia e dùng vector , kết thúc = dấu " . " .

vector < string> a;
do
	{
		cin >> temp;
		a.push_back(temp);
	} while (temp != ".");

trong map < node , set < data> > , trc hết tìm đỉnh bắt đầu thì e tìm đc rồi

    for (int i = 0, j = i + 1; i < size - 2; i++, j++)
    g.find(a[i])

bây giờ cái phần set ( g.find(a[i])->second ) làm sao tìm đc a[j] để cộng độ dài được a !???
chỉ tìm phần first trong set thôi , sau đó cộng cái phần second ấy

Nam viết 22:27 ngày 30/09/2018

Ông share cho t cái code đc không. T đang bí chỗ nhập của bài này @@~

Đông viết 22:35 ngày 30/09/2018

phần nhập úp lên r mà !?? cái đầu tiên đó !

Khôi Trần viết 22:36 ngày 30/09/2018

bài này nếu để làm gì nữa thì tổ chức dữ liệu như banj là được rồi còn chỉ để làm bài này thì chỉ cần add map rôic check map và map khi reserse cặp cạnh thôi

Gió viết 22:32 ngày 30/09/2018

Nếu liên quan đến độ dài và tìm cạnh … Thì có thể cài đồ thị như sau

map<Node,map<Node,int>> g;
// Duong di u-v-u
int length(Node & u,Node & v){
     if(g[u].find(v)!=g[u].end() and g[v].find(u)!=g[v].end()) return g[u][v]+g[v][u];
     else return -1; // không có đường đi u->v->u
}

Bạn nên tìm hiểu các hàm trong stl

Đông viết 22:24 ngày 30/09/2018

Chứ mình ko tìm theo phần tử đầu của lớp pair trong set đc hả a !?? a có tài liệu nào hay về cách dùng thư viện stl ko ạ, trên cplusplus.com toàn vd tổng quát, ko nói nhiều về các object mình tự định nghĩa ! tks a nhìu ạ

Đông viết 22:35 ngày 30/09/2018

Mà nếu mình dùng map<Node,map<Node,int>> g; thì lúc insert có phải thêm hàm so sánh ko a !?
Anh chỉ cho e cách insert trong map kiểu như vậy nha a !

Gió viết 22:27 ngày 30/09/2018

map có operator [] nên có thể dễ dàng insert vào

void addEdge(Node u,Node v,int w){
     g[u][v]=w;
}

Đông viết 22:25 ngày 30/09/2018

Dạ , cảm ơn a để đêm nay e code theo hướng đó có mấy bài mà code đi code lại mấy kiểu rồi , chỉ có code theo kiểu như vậy mới tìm kiếm nhah đc , ko phải duyệt tuần tự như mảng , lúc nộp bài còn tính lỗi time limited nữa !!

Đông viết 22:31 ngày 30/09/2018

E làm xog gần hết bài tập rồi , tks a nhiều

Bây giờ e muốn tạo 1 kiểu dữ liệu , vd :

     typedef struct data
        {
        string name;
        int color;
        }

rồi dùng

map < data, data > Graph;

liệu có dùng được ko !? và insert thì viết như thế nào ah. !

hay là phải viết riêng hàm insert , mà ko gọi đc hàm trong stl !

Mario viết 22:27 ngày 30/09/2018

Hi @DoNg,
Mình xin trả lời câu hỏi của bạn :

map < data, data > Graph;

liệu có dùng được ko !?

Về mặt kỹ thuật:

Cách dùng này là không được vì kiểu của khóa của map<kiểu khóa, kiểu giá trị> phải là kiểu dữ liệu so sánh được. Trong đó data là cấu trúc dữ liệu bạn tự định nghĩa, chưa có toán tử thứ tự.
Để giải quyết, bạn cần xây dựng toán tử thứ tự cho struct data:

typedef struct data
        {
        string name;
        int color;
        bool operator <(const data &Data) 
                {
                      return (this->name < Data.name);
                }
        }

Điều này có nghĩa là thứ tự được quyết định giữa 2 đối tượng kiểu data dựa vào thuộc tính name của nó, trong đó phép so sánh này giữa 2 kiểu dữ liệu string lại được quyết định nhờ operator khác được định nghĩa trong lớp string.
Ngoài ra, thuộc tính định thứ tự còn là thuộc tính quyết định sự duy nhất của khóa.
Ví dụ, nếu bạn so sánh dựa vào thuộc tính name thì có nghĩa là hai node A , B khác nhau sẽ được map < data, data > Graph; coi là khác nhau nếu A.name != B.name, còn các thuộc tính khác không có giá trị quyết định sự khác nhau, ngoài ra, nếu A.name == B.name thì A,B khi truyền vào map làm key thì được coi như là một.
Theo mình thì nên so sánh dựa trên địa chỉ của data được cấp phát:
return (this < &Data); // không chắc nữa
Truy cập hay chèn phần tử vào map có thể dùng qua toán tử [];

Về mặt ý nghĩa:
Nếu bạn dùng map < data, data > Graph; để lưu danh sách cạnh thì có thể bị mất thông tin vì data đầu tiên trong map là khóa, do đó nó được lưu DUY NHẤT, nếu gán nó lần 2 thì nó chồng lên lần đầu:
VD:Lưu cạnh AB và AC:
Graph[A]=B
Graph[A]=C
==> Graph[A] cho kết quả là C, C đã ghi đè lên B.
Kiểm tra Graph.size()=1 :’(
Vì thế mình khuyên bạn gói 2 kiểu data sang 1 bên key:
map<string,bool>, trong đó string là ghép của (A.name+B.name)
S= (A.name+B.Name); map[S]=true; S= (A.name+C.Name); map[S]=true;
Kiểm tra: Graph.size()=2 // (^_^)
Nếu không mình khuyên bạn dùng pair<string,string> làm khóa.