Pagini recente » Cod sursa (job #2830375) | Cod sursa (job #1722548) | Cod sursa (job #2739870) | Cod sursa (job #2374176) | Cod sursa (job #2926239)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector<vector<int>> adj, revAdj, components;
vector<int> visited;
stack<int> stiva;
void DFS1(int nod)
{
visited[nod] = 1;
for(int i = 0; i < adj[nod].size(); i++)
if(visited[adj[nod][i]] == 0)
DFS1(adj[nod][i]);
stiva.push(nod);
}
void DFS2(int nod, int nrComp)
{
components[nrComp].push_back(nod);
visited[nod] = 1;
for(int i = 0; i < revAdj[nod].size(); i++)
if(visited[revAdj[nod][i]] == 0)
DFS2(revAdj[nod][i], nrComp);
}
int main()
{
int n, m, nod1, nod2, i, j, nrComp = 0, nod;
in >> n >> m;
adj.resize(n + 1);
revAdj.resize(n + 1);
visited.resize(n + 1);
for(i = 1; i <= m; i++)
{
in >> nod1 >> nod2;
adj[nod1].push_back(nod2);
revAdj[nod2].push_back(nod1);
}
for(i = 1; i <= n; i++)
if(visited[i] == 0)
DFS1(i);
for(i = 1; i <= n; i++)
visited[i] = 0;
while(!stiva.empty())
{
nod = stiva.top();
stiva.pop();
if(visited[nod] == 0)
{
components.push_back({});
DFS2(nod, nrComp);
nrComp++;
}
}
out << nrComp << '\n';
for(i = 0; i < components.size(); i++)
{
for(j = 0; j < components[i].size(); j++)
out << components[i][j] << " ";
out << '\n';
}
return 0;
}