Pagini recente » Monitorul de evaluare | Cod sursa (job #244197) | Cod sursa (job #3315218) | Cod sursa (job #3036987) | Cod sursa (job #3336573)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int N = 1e5;
vector<int> lista_ad[N + 1], transpus[N + 1], ctc[N + 1];
stack<int> ordine; // timpi iesire
bool vizitat[N + 1];
int nr_ctc = 1;
void dfs(int start)
{
for (int j : lista_ad[start])
{
if (!vizitat[j])
{
vizitat[j] = true;
dfs(j);
ordine.push(start);
}
}
}
void dfs_transpus(int start_t, int nr_ctc)
{
for (int j : transpus[start_t])
{
if (!vizitat[j])
{
vizitat[j] = true;
dfs_transpus(j, nr_ctc);
ctc[nr_ctc].push_back(j);
}
}
}
int main()
{
int n, m;
in >> n >> m;
int u, v;
for (int i = 0; i < m; i++)
{
in >> u >> v;
lista_ad[u].push_back(v);
transpus[v].push_back(u);
}
for (int i = 1; i <= n; i++)
vizitat[i] = false;
vizitat[1] = true;
dfs(1);
for (int i = 2; i <= n; i++)
{
if (!vizitat[i])
dfs(i);
}
// acum am efectuat prima parcurgere DFS pe graful original G si am obtinut ordinea nodurilor
// in functie de timpii de iesire
for (int i = 1; i <= n; i++)
vizitat[i] = false;
while (!ordine.empty())
{
int start_transpus = ordine.top();
ordine.pop();
if (!vizitat[start_transpus])
{
vizitat[start_transpus] = true;
ctc[nr_ctc].push_back(start_transpus);
dfs_transpus(start_transpus, nr_ctc);
nr_ctc++;
}
}
out << nr_ctc - 1 << '\n';
for (int i = 1; i < nr_ctc; i++)
{
for (size_t j = 0; j < ctc[i].size(); j++)
out << ctc[i][j] << " ";
if(i != nr_ctc - 1)
out << '\n';
}
return 0;
}