Pagini recente » Cod sursa (job #2648463) | Cod sursa (job #2108383) | Cod sursa (job #3297983) | Cod sursa (job #1742639) | Cod sursa (job #2676240)
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
#define NMax 100005
vector<int>G[NMax], H[NMax];
stack<int> S;
vector<int>rez[101];
int n, m,beenThere[101],nrCTC;
void read()
{
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
fin >> x >> y;
G[x].push_back(y);
H[y].push_back(x);
}
}
void dfs(int x)
{
beenThere[x] = 1;
//zona 1 = zona cand a fost descoperit nodul
for (unsigned int i=0;i<G[x].size();i++)
{ //zona 2
int vecin=G[x][i];
if(!beenThere[vecin])
dfs(vecin);
//zona 3
}
S.push(x);
//zona 4 = zona in care se gata toti vecinii de vizitat a nodului curent pentru care s-a fct dfs
}
void dfsGT(int x)
{
beenThere[x] = 2;
rez[nrCTC].push_back(x);
for (unsigned int i=0;i<H[x].size();i++)
{
int vecin=H[x][i];
if(beenThere[vecin]==1)
dfsGT(vecin);
}
}
void solve()
{
for (int i = 1; i <= n; i++)
if (!beenThere[i])
dfs(i);
while (!S.empty())
{
int k = S.top();
if (beenThere[k] == 1)
{
nrCTC++;
dfsGT(k);
}
S.pop();
}
}
void print()
{
for(int i=1;i<=n;i++)
sort(rez[i].begin(),rez[i].end());
fout << nrCTC << endl;
for (int i = 1; i <= nrCTC; i++)
{
for (unsigned int j = 0; j < rez[i].size(); j++) fout << rez[i][j] << " ";
fout << endl;
}
}
int main()
{
read();
solve();
print();
return 0;
}