Pagini recente » Cod sursa (job #682221) | Cod sursa (job #1430767) | Cod sursa (job #530181) | Cod sursa (job #2020273) | Cod sursa (job #2928780)
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
int k, n, m, x, y;
stack <int> s;
bool visited[100001] = {false};
vector <vector <int>> adjList1;
vector <vector <int>> adjList2;
vector <vector<int>> sol;
void dfs(int i, bool visited[])
{
visited[i] = true;
sol[k].push_back(i);
for(auto j : adjList2[i])
if(!visited[j])
dfs(j, visited);
}
void order(int j, bool visited[], stack <int> &s)
{
visited[j] = true;
for(auto i : adjList1[j])
if(!visited[i])
order(i, visited, s);
s.push(j);
}
void printCTC()
{
for(int i = 1; i <= n; i++)
if(!visited[i])
order(i, visited, s);
for(int i = 1; i <= n; i++)
visited[i] = false;
while(!s.empty())
{
int a = s.top();
s.pop();
if(!visited[a])
{
k++;
dfs(a, visited);
}
}
}
int main()
{
f>>n>>m;
adjList1.resize(n + 1);
adjList2.resize(n + 1);
sol.resize(n + 1);
for(int i = 1; i <= m; i++)
{
f>>x>>y;
adjList1[x].push_back(y);
adjList2[y].push_back(x);
}
/* for(auto i : adjList1)
{
for(auto j : i)
cout<<j<<' ';
cout<<endl;
}*/
printCTC();
g<<k<<'\n';
for(int i = 1; i <= k; i++)
{
for(auto j : sol[i])
g<<j<<' ';
g<<'\n';
}
return 0;
}