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

DoNg · April 10, 2016, 10:04am

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++)
{
	...
}

Khuong_Truong · April 14, 2016, 8:26am

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

DoNg · April 14, 2016, 10:27am

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

Gio · April 14, 2016, 10:14am

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

DoNg · April 14, 2016, 10:30am

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 !!

DoNg · April 14, 2016, 1:22pm

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

Gio · April 14, 2016, 2:44pm

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;
}

DoNg · April 14, 2016, 2:50pm

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 · April 14, 2016, 3:11pm

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!

DoNg · April 15, 2016, 3:15am

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

DoNg · April 15, 2016, 3:24am

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

H.Nam · March 24, 2018, 1:25am

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

DoNg · April 15, 2016, 9:26am

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

JuniorK · April 15, 2016, 9:42am

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

Gio · April 15, 2016, 9:53am

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

DoNg · April 15, 2016, 10:35am

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̣

DoNg · April 15, 2016, 11:33am

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 !

Gio · April 15, 2016, 11:49am

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;
}

DoNg · April 15, 2016, 1:11pm

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 !!

DoNg · April 17, 2016, 5:05pm

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 !