Pagini recente » Cod sursa (job #3312185) | Cod sursa (job #3329436) | Cod sursa (job #3324485) | Cod sursa (job #1443867) | Cod sursa (job #3326924)
#include <fstream>
#include <stack>
#include <vector>
#include <algorithm>
#define NMAX 100002
using namespace std;
ifstream fin ("ctc.in");
ofstream fout ("ctc.out");
int n, m, nrCTC;
bool vizitat[NMAX];
vector<vector<int>> Graf;
vector<vector<int>> GrafT;
stack<int> stiva;
vector<vector<int>> compTC;
void DFS1(int nod);
void DFS2(int nod);
int main()
{
int i, j, x, y;
//citire si graf transpus pentru CTC
fin>>n>>m;
Graf.resize(n + 2); GrafT.resize(n + 2); compTC.resize(n + 2);
for(i = 1; i <= m; i++)
{
fin>>x>>y;
Graf[x].push_back(y);
GrafT[y].push_back(x);
}
for(i = 1; i <= n; i++) //umplem stiva, primul DFS
if(!vizitat[i])
DFS1(i);
for(i = 1; i <= n; i++) vizitat[i] = 0;
while(stiva.size())
{
x = stiva.top(); stiva.pop();
if(!vizitat[x])
{
nrCTC++;
DFS2(x);
}
}
fout<<nrCTC<<'\n';
for(i = 0; i < compTC.size(); i++)
if(compTC[i].size() > 0)
{
for(j = 0; j < compTC[i].size(); j++)
fout<<compTC[i][j]<<' ';
fout<<'\n';
}
return 0;
}
void DFS2(int nod)
{
vizitat[nod] = 1;
for(int i = 0; i < GrafT[nod].size(); i++)
if(!vizitat[GrafT[nod][i]])
{
DFS2(GrafT[nod][i]);
}
compTC[nrCTC].push_back(nod);
}
void DFS1(int nod)
{
vizitat[nod] = 1;
for(int i = 0; i < Graf[nod].size(); i++)
if(!vizitat[Graf[nod][i]])
{
DFS1(Graf[nod][i]);
}
stiva.push(nod);
}