Pagini recente » Cod sursa (job #2325601) | Cod sursa (job #2546581) | Cod sursa (job #748154) | Cod sursa (job #2411796) | Cod sursa (job #3254269)
#include <bits/stdc++.h>
using namespace std;
ifstream f ("ctc.in");
ofstream g ("ctc.out");
const int nmax = 100000;
vector <int> vecini[nmax+5], veciniGT[nmax+5], sortare, componente[nmax + 5];
int vizitat[nmax + 5];
void dfs(int node, vector <int> muchii[nmax+5], vector <int> &Sortare)
{
///sortare o sa fie la final vectoul cu ordinea varfurilor (prima data)
///a doua data o sa fie componenta tare conexa in care pun varfurile
vizitat[node] = 1;
int i;
for(i = 0; i < muchii[node].size(); ++i)
{
int nodnou = muchii[node][i];
if(!vizitat[nodnou])
{
dfs(nodnou, muchii, Sortare);
}
}
Sortare.push_back(node);
}
int main()
{
int n, m, i, x, y, conexe = 0;
f >> n >> m;
for(i = 1; i <= m; ++i)
{
f >> x >> y;
vecini[x].push_back(y);
veciniGT[y].push_back(x);
}
///dfs 1
///fac vizitat pe 0
///dfs 2
for(i = 1; i <= n; ++i)
{
if(!vizitat[i])
{
dfs(i, vecini, sortare);
}
}
for(i = 1; i <= n; ++i)
{
vizitat[i] = 0;
}
for(i = n - 1; i >= 0; --i)
{
if(!vizitat[sortare[i]])
{
++conexe;
dfs(sortare[i], veciniGT, componente[conexe]);
}
}
g << conexe << "\n";
for(i = 1; i <= conexe; ++i)
{
int j;
for(j = 0; j < componente[i].size(); ++j)
{
g << componente[i][j] << " ";
}
g << "\n";
}
return 0;
}