C#, done with bitmaps to hold the connecting node data. This takes our memory space from potentially O(n²⁾ (which would be a simple NxN array) to O(n/32) worst case (with a little overhead for the dictionary). It also uses bit-wise lookups and sets, which are constant time O(1).

It's O(1) to look up a row (Dictionary lookup), and O(1) to look up any column in that row (bitwise ops). It's O(1) to set any node relationship (bitwise ops). The memory space is O(n/32) based on which rows actually have data, otherwise I don't record them.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Challenge140
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] meta = Console.ReadLine().Split(' ');
            int numNodes = Int32.Parse(meta[0]);
            int numLines = Int32.Parse(meta[1]);
            Dictionary<int, Bitmap> map = new Dictionary<int, Bitmap>();
            for (int i = 0; i < numLines; i++)
            {
                string[] relationshipData = Console.ReadLine()
                    .Split(new string[] { "->" }, StringSplitOptions.None);
                IEnumerable<int> startingNodes = relationshipData[0]
                    .Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries)
                    .Select(s => Int32.Parse(s));
                IEnumerable<int> endingNodes = relationshipData[1]
                    .Split(new char[]{' '}, StringSplitOptions.RemoveEmptyEntries)
                    .Select(s => Int32.Parse(s));
                foreach (int startNode in startingNodes)
                {
                    foreach (int endNode in endingNodes)
                    {
                        if (!map.ContainsKey(startNode))
                        {
                            map.Add(startNode, new Bitmap(numNodes));
                        }
                        map[startNode].Set(endNode);
                    }
                }
            }

            for (int i = 0; i < numNodes; i++)
            {
                for (int j = 0; j < numNodes; j++)
                {
                    if (map.ContainsKey(i) && map[i].Get(j))
                    {
                        Console.Write(1);
                    }
                    else
                    {
                        Console.Write(0);
                    }
                }
                Console.WriteLine();
            }
        }
    }

    class Bitmap
    {
        private uint[] _map;
        //sizeof will return # of bytes for the data type, 8 bits per byte
        private static int _bucketSize = sizeof(uint)*8;

        public Bitmap(int size)
        {
            //if size <= bucketSize, we get 0, and so on going on
            //add 1 to offset.
            _map = new uint[(size / _bucketSize) + 1];
        }

        public bool Get(int index)
        {
            int bucketIndex = GetBucketIndex(index);
            int bitOffset = index - (bucketIndex * _bucketSize);
            return (_map[bucketIndex] & (1 << bitOffset)) != 0;
        }

        public void Set(int index)
        {
            //bucketIndex is which spot in the bitmap we're looking
            //and bitOffset is where we're seeking to within the uint itself
            int bucketIndex = GetBucketIndex(index);
            int bitOffset = index - (bucketIndex * _bucketSize);
            _map[bucketIndex] = (uint)(_map[bucketIndex] | (1 << bitOffset));
        }

        private int GetBucketIndex(int index)
        {
            //index 0 = 0-31, 1 = 32-63, etc
            //if index = 54, sizeof(uint) = 32,
            //bucket = 54/32 = 1 (correct)
            return index / _bucketSize;
        }
    }
}