Pagini recente » Cod sursa (job #3228643) | Cod sursa (job #999128) | Cod sursa (job #1339233) | Cod sursa (job #1357921) | Cod sursa (job #2797874)
#include <iostream>
#include <stack>
#include <fstream>
#include <vector>
#define N 100001
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector <int> conexe[N];
stack <int> stiva;
bool visited_conex[N];
bool visited[N];
class Graph {
public:
vector <int> adiacenta[N];
vector <int> adiacenta_conex[N];
void addEdge(int x, int y);
void SolveConexe();
void DFS_CNX(int vf, int ctc);
void DFS(int vf);
};
void Graph::addEdge(int x, int y)
{
adiacenta[x].push_back(y);
adiacenta_conex[y].push_back(x);
}
void Graph::SolveConexe()
{
int vf, ctc = 0;
while(!stiva.empty())
{
stiva.pop();
vf = stiva.top();
if(visited_conex[vf] == 0)
{
ctc += 1;
DFS_CNX(vf, ctc);
}
}
fout<<ctc<<endl;
for(int i = 1; i <= ctc; ++i)
{
for(int j = 0; j < conexe[i].size(); ++j)
{
fout<<conexe[i][j]<<" ";
}
fout<<endl;
}
}
void Graph::DFS(int vf)
{
visited[vf] = true;
for(int i = 0; i < adiacenta[vf].size(); ++i)
if(!visited[adiacenta[vf][i]])
DFS(adiacenta[vf][i]);
stiva.push(vf);
}
void Graph::DFS_CNX(int vf,int ctc)
{
visited_conex[vf] = 1;
conexe[ctc].push_back(vf);
for(int i = 0; i < adiacenta_conex[vf].size(); ++i)
if(visited_conex[adiacenta_conex[vf][i]] == 0)
DFS_CNX(adiacenta_conex[vf][i], ctc);
}
int main()
{
int n, m, n1, n2;
cin >> n >> m;
Graph g;
for(int i = 0; i < m; ++i)
{
cin >> n1 >> n2;
g.addEdge(n1,n2);
}
for(int i = 1; i <= n; ++i)
{
if(!visited[i])
g.DFS(i);
}
g.SolveConexe();
return 0;
}