Pagini recente » Cod sursa (job #2769136) | Cod sursa (job #2855467) | Cod sursa (job #912068) | Cod sursa (job #651702) | Cod sursa (job #2665382)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int culoare;
vector <int> rezultat[10000000];
void DFS1(int current, vector <bool>& visited, vector <int> fii[])
{
visited[current] = 1;
for(int j = 0; j < fii[current].size(); ++j)
{
if(visited[fii[current][j]] == false)
DFS1(fii[current][j], visited, fii);
}
}
void DFS2(int node, vector <bool>& visited, vector <int> parinti[])
{
visited[node] = 1;
rezultat[culoare].push_back(node);
{
for(int i = 0; i <= parinti[node].size(); ++i)
if(visited[parinti[node][i]] == 0)
DFS2(parinti[node][i], visited, parinti);
}
}
// Kosaraju
int main()
{
int n, m;
vector <int> fii[n+1];
vector <int> parinti[n+1];
fin >> n >> m;
for(int i = 0; i < m; ++i)
{
int x, y;
fin >> x >> y;
fii[x].push_back(y);
parinti[y].push_back(x);
}
vector <bool> visited(n+1, 0);
stack <int> stiva;
for(int i = 1; i <= n; ++i)
{
if(visited[i] == 0)
DFS1(i, visited, fii);
}
for(int i = 1; i <= n; ++i)
{
visited[i] = false;
}
while(stiva.empty() == false)
{
int node = stiva.top();
if(visited[node] == false)
{
culoare++;
DFS2(node, visited, parinti);
}
stiva.pop();
}
fout << culoare << endl;
for(int i = 1; i <= culoare; ++i)
{
for (int j = 0; j < rezultat[i].size(); ++j)
fout << rezultat[i][j] << " ";
fout << endl;
}
return 0;
}