用C++实现以下功能

(1)输入一个无向图，打印出它的所有连通分量。如
下示例，
连通分量有2个，分别为{1,2,4,5}, {3,6}
(2)输入一个有向图，打印出它的所有强连通分量。
如下示例，
强连通分量有3个，分别为{1}, {4}, {2,5,3,6}

输入图的格式是什么？

第二题：打印出有向图的所有强连通分量。

#include<iostream>
#include<stack>
#include<vector>
using namespace std;
int n,m,cnt,cntb;
vector<int> edge[101];
vector<int> belong[101];
bool instack[101];
int dfn[101];
int low[101];//LOW［］作为每个点在这颗树中的，最小的子树的根，每次保证最小，like它的父亲结点的时间戳这种感觉。如果它自己的LOW［］最小，那这个点就应该从新分配，变成这个强连通分量子树的根节点。
stack<int> s;
void Tarjan(int u) //tarjan算法
{
    ++cnt;
    dfn[u]=low[u]=cnt;//DFN［］作为这个点搜索的次序编号（时间戳），简单来说就是 第几个被搜索到的
    s.push(u);
    instack[u]=true;
    for(int i=0;i<edge[u].size();++i)
    {
        int v=edge[u][i];
        if(!dfn[v])//如果节点v未被访问过
        {
            Tarjan(v);// 继续向下找
            low[u]=min(low[u],low[v]);
        }
        else if(instack[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])//如果节点u是强连通分量的根
    {
        ++cntb;
        int node;
        do
        {
            node=s.top();
            s.pop();
            instack[node]=false;
            belong[cntb].push_back(node);
        }while(node!=u);
    }
}
int main()
{
    cout<<"求有向图强连通分量：\n";
    cout<<"请输入节点的个数n：";

    cin>>n;
    cout<<"请输入边的条数m：";
    cin>>m;

    cout<<"请输入"<<m<<"条边：\n";
    for(int i=1;i<=m;++i)
    {
        int u,v;
        cin>>u>>v;
        edge[u].push_back(v);//输入边
    }
    Tarjan(1);
    for(int i=1;i<=cntb;++i)
    {
        cout<<"连通分量"<<i<<" : ";
        for(int j=0;j<belong[i].size();++j)
            cout<<belong[i][j]<<" ";
        cout<<endl;
    }
    return 0;
}

无向图能求了， 有向图还有问题。。。

好的

#include <iostream>
#include <vector>
#include <cassert>
using namespace std;

// 稀疏图 - 邻接表
class SparseGraph{

private:
    int n, m;       // 节点数和边数
    bool directed;  // 是否为有向图
    vector<vector<int> > g;  // 图的具体数据

public:
    // 构造函数
    SparseGraph( int n , bool directed ){
        assert( n >= 0 );
        this->n = n;
        this->m = 0;    // 初始化没有任何边
        this->directed = directed;
        // g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
        g = vector<vector<int> >(n, vector<int>());
    }

    ~SparseGraph(){ }

    int V(){ return n;} // 返回节点个数
    int E(){ return m;} // 返回边的个数

    // 向图中添加一个边
    void addEdge( int v, int w ){

        assert( v >= 0 && v < n );
        assert( w > 0 && w < n );

        g[v].push_back(w);
        if( v != w && !directed )
            g[w].push_back(v);
            
        m ++;
    }

    // 验证图中是否有从v到w的边
    bool hasEdge( int v , int w ){

        assert( v >= 0 && v < n );
        assert( w >= 0 && w < n );

        for( int i = 0 ; i < g[v].size() ; i ++ )
            if( g[v][i] == w )
                return true;
        return false;
    }

    // 显示图的信息
    void show(){

        for( int i = 0 ; i < n ; i ++ ){
            cout<<"vertex "<<i<<":\t";
            for( int j = 0 ; j < g[i].size() ; j ++ )
                cout<<g[i][j]<<"\t";
            cout<<endl;
        }
    }

    // 邻边迭代器, 传入一个图和一个顶点,
    // 迭代在这个图中和这个顶点向连的所有顶点
    class adjIterator{
    private:
        SparseGraph &G; // 图G的引用
        int v;
        int index;

    public:
        // 构造函数
        adjIterator(SparseGraph &graph, int v): G(graph){
            this->v = v;
            this->index = 0;
        }

        ~adjIterator(){}

        // 返回图G中与顶点v相连接的第一个顶点
        int begin(){
            index = 0;
            if( G.g[v].size() )
                return G.g[v][index];
            // 若没有顶点和v相连接, 则返回-1
            return -1;
        }

        // 返回图G中与顶点v相连接的下一个顶点
        int next(){
            index ++;
            if( index < G.g[v].size() )
                return G.g[v][index];
            // 若没有顶点和v相连接, 则返回-1
            return -1;
        }

        // 查看是否已经迭代完了图G中与顶点v相连接的所有顶点
        bool end(){
            return index >= G.g[v].size();
        }
    };
};


// 求无权图的联通分量
template <typename Graph>
class Component{

private:
    Graph &G;       // 图的引用
    bool *visited;  // 记录dfs的过程中节点是否被访问
    int ccount;     // 记录联通分量个数
    int *id;        // 每个节点所对应的联通分量标记

    // 图的深度优先遍历
    void dfs( int v ){
        visited[v] = true;
        id[v] = ccount;
        typename Graph::adjIterator adj(G, v);
        for( int i = adj.begin() ; !adj.end() ; i = adj.next() ){
            if( !visited[i] )
                dfs(i);
        }
    }

public:
    // 构造函数, 求出无权图的联通分量
    Component(Graph &graph): G(graph){

        // 算法初始化
        visited = new bool[G.V()];
        id = new int[G.V()];
        ccount = 0;
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            id[i] = -1;
        }

        // 求图的联通分量
        for( int i = 0 ; i < G.V() ; i ++ )
            if( !visited[i] ){
                dfs(i);
                ccount ++;
            }
    }

    // 析构函数
    ~Component(){
        delete[] visited;
        delete[] id;
    }

    // 返回图的联通分量个数
    void showComponents(){
        vector<vector<int> > components;
        components = vector<vector<int> > (G.V(), vector<int>(0)); 
        
        for(int i = 1; i < G.V(); i++)
            if(id[i] != -1)
                components[id[i]].push_back(i);
        
        cout << endl;
        cout << "联通分量分别是：" << endl; 
        for(int i = 1; i < components.size(); i++){
            for(int j = 0; j < components[i].size(); j++)
                cout << components[i][j] << " ";
            if (components[i].size() != 0)
                cout << endl;
        }

    }

    // 查询点v和点w是否联通
    bool isConnected( int v , int w ){
        assert( v >= 0 && v < G.V() );
        assert( w >= 0 && w < G.V() );
        return id[v] == id[w];
    }
};



void calculateComponents(){
    int direct;
    int V, E;  // 记录定点数和边数 
    
    cout << "请选择：" << endl;
    cout << "0. 无向图" << endl;
    cout << "1. 有向图" << endl;
    cin >> direct;
    
    cout << "请输入顶点数， 边数:" << endl;
    cin >> V >> E;
    cout << "请输入 " << E << " 条边" << endl;
    
    SparseGraph gragh = SparseGraph(V + 1, bool(direct));
    int node1, node2;      // 记录顶点 , 编号从1开始 
    for (int i = 0; i < E; i++){  // 构造图 
        cin >> node1 >> node2;
        gragh.addEdge(node1, node2);
    }
    
    Component<SparseGraph> component(gragh);
    component.showComponents();
}

int main(){
    calculateComponents();
}